1000
-8159166 -7278249 -6638549 -5827264 -5907312 -5050912 -4839331 -4830138 -4349788 -4092278 -4051035 -3873194 -3895656 -3490511 -3137869 -2415933 -2313421 -2161568 -1493916 -1128050 -302872 -99316 -18053104 -18084152 -17562178 -17053937 -16192805 -15369394 -14698440 -13812371 -13179723 -13157563 -12967609 -12410773 -12476731 -12190345 -11646806 -11044084 -10336223 -10017571 -9750837 -9135172 -8721911 -8748133 -28198631 -27541410 -27614673 -27138571 -26305578 -25829896 -25765810 -25523342 -24889204 -24080507 -23748668 -22903943 -22499854 -22015681 -21820897 -21340229 -21031508 -20595124 -19812073 -19491437 -19241913 -18613507 -40294069 -39907036 -39043999 -38571961 -37788284 -37302232 -36815766 -36301061 -35834587 -35108235 -34451472 -33879657 -33226956 -32462924 -32555761 -31790535 -31267936 -30534025 -29911796 -29692951 -28920058 -28638402 -49604610 -49108233 -48243090 -48115401 -47272920 -47042612 -46803233 -46691365 -46151924 -45527565 -45241866 -44467433 -44211204 -43849534 -43153126 -43236748 -42505227 -41606535 -41498143 -41529043 -41558811 -41099896 -59879259 -59036753 -58262769 -57860360 -57649879 -57094887 -56364949 -56313039 -55892357 -55506127 -55194632 -54580187 -54416580 -53672070 -52931861 -52649845 -52145097 -51779228 -51093528 -50822901 -50493978 -50249781 -67988192 -67822152 -67060747 -66987878 -66461967 -66237459 -65844648 -65126961 -65123193 -64785251 -64731271 -64258444 -63783279 -63752515 -63029409 -62206990 -61843286 -61213463 -60806919 -60148197 -60236263 -60215253 -78300225 -77803951 -77330808 -76910648 -76458778 -76012860 -75439500 -74907794 -74238772 -74009324 -73172528 -72966610 -72653713 -71986140 -71672336 -70975396 -70209993 -70050306 -69513966 -69267972 -68582534 -68228774 -87238636 -86524386 -86110280 -85682983 -84994558 -84372653 -84332567 -84326905 -83811891 -83473285 -83247490 -82744950 -82693823 -82045018 -81991334 -81349594 -81323117 -80554165 -80587065 -80414454 -79549530 -79199599 -95270359 -95353439 -95185990 -95101940 -94443065 -93677509 -92786640 -91914939 -91587358 -91188303 -91079837 -91046653 -90950763 -90999937 -90297151 -89999242 -89137759 -88568821 -88356443 -88208068 -87884743 -87845719 -100620384 -100407978 -100085924 -99269217 -98806499 -98508696 -98523726 -98412119 -97930467 -97784142 -97703457 -97115784 -97146365 -96617509 -96621921 -96508692 -96285533 -96250502 -96019172 -95907693 -95341827 -95220015 -110185119 -110094812 -109265152 -108561017 -108595770 -108305855 -107804618 -107366669 -107348494 -106628414 -106192127 -105416997 -105400614 -105397057 -104967958 -104447542 -104323042 -103795460 -102962263 -102249860 -101578484 -101424536 -118269063 -118238277 -117963854 -117150010 -117151371 -117237563 -116457854 -116286198 -115882975 -115444972 -115024409 -114437935 -114449728 -114120211 -113891272 -113483435 -113087295 -113007101 -112112644 -111566784 -110799809 -110804685 -127343219 -126659834 -126192034 -125501533 -124684155 -124230979 -124172473 -123860639 -123433510 -122575123 -122273688 -122011236 -121452644 -121274807 -121050841 -120630786 -120306231 -120329869 -120256872 -119693987 -119576503 -118753548 -135380163 -135060206 -134483978 -134259761 -134300512 -133635481 -133621681 -133074712 -132712082 -132062181 -131406458 -130874676 -130903737 -130709423 -130116208 -129683885 -129187338 -129065130 -128763058 -128369791 -128054734 -128082715 -145014268 -144308121 -143796278 -143766018 -143497257 -142783797 -142151660 -141439066 -140614743 -140015031 -139961274 -139434342 -138739033 -138369104 -137866143 -137549729 -137362904 -136943108 -136943083 -136350296 -135984782 -135562475 -153262991 -152849849 -152331893 -151863642 -151924319 -151504199 -151258886 -151249557 -151091068 -150763727 -150572707 -150315567 -150225513 -149327058 -148457210 -148078004 -147617919 -147162406 -147030032 -146589638 -145701998 -145462455 -161715201 -160880571 -160884454 -160929837 -160937104 -160084252 -159195922 -158317638 -158215473 -157862325 -157467354 -157217976 -156919196 -156777884 -156765920 -156014946 -155680350 -155387001 -155333465 -155112693 -154535829 -153918088 -170574582 -170452937 -169594043 -169579612 -168874710 -168791341 -168512814 -167808279 -167136752 -166955289 -166717195 -166769744 -166646761 -166610992 -165724517 -164918776 -164722817 -163830830 -163738787 -163405652 -162643529 -162494305 -179267667 -178687529 -177903716 -177520934 -176654083 -176608131 -176589216 -175710321 -175785932 -175501470 -175331441 -175383341 -175312777 -174882736 -174301594 -173862813 -173884842 -173281351 -173126327 -172854808 -172122035 -171396933 -187653843 -187071570 -186617049 -185969836 -185639333 -185425603 -184855209 -184757079 -184853904 -184650748 -184494390 -184340692 -184232864 -183617670 -182744694 -181979896 -181391416 -181441282 -181498742 -181177643 -180469067 -179918239 -193625117 -193677446 -193487484 -192801045 -192263217 -192076498 -191764774 -191200515 -191063961 -191126554 -191116816 -191029103 -190918931 -190483000 -190039075 -189825856 -188971763 -188829663 -188482334 -187888562 -187920482 -187814483 -199796056 -199066223 -198592224 -197955157 -198015688 -197357464 -197301972 -197038581 -197106902 -196640532 -196262251 -196131011 -195775601 -194966446 -194633279 -194452309 0 815431 1009136 1892613 2295505 2684109 3497732 4043496 4227869 4925302 5161704 5236337 5213489 5648058 6064208 6393121 6556845 6789608 7201929 7421073 7853574 8088865 8110832 8352876 9232196 9805914 10011000 10131314 10992388 11411230 11955240 11936694 12246197 13097416 13601368 13641567 14014877 14348747 14514362 15189802 15821973 16683245 17441870 17994789 18892488 18882375 19353837 19915445 20375288 21235399 22022783 22330705 22416313 22376494 23021509 23624965 23594868 23845906 24110159 24818671 25327908 25707484 25846726 25786309 26139164 26297355 26331236 26861581 27162559 27365615 27754166 28539618 28965445 29075310 29386016 29721334 30103549 30953027 31050073 31875722 32315205 32993081 33807338 34022071 34065747 34339443 34393587 34826280 35227695 35421799 36108261 36418396 37007029 37250653 37662152 38172584 38696343 38630964 38884726 39433075 39833625 40219485 40428829 40892471 41284946 41734365 42069632 42778821 43299376 44188302 44530678 45043137 45230388 46020702 46818665 46986914 47798706 48232206 48722135 49100978 49550866 50118004 50546068 50829972 51013906 51479290 52309511 53170490 53754178 54159325 54955881 55540010 56067845 55988654 56834249 57542914 57580054 58460755 58855241 59473839 59963776 60039814 60300768 60664886 60834211 61158484 61530714 61478256 62242166 62688735 63049747 62975813 63754494 63803739 63985598 64324215 64637851 64814676 65034852 65768410 65707964 66317415 67061022 67216533 67304998 67917764 68521498 69373154 69456689 69736306 69956379 69859155 70201034 70519818 70842744 71390410 72057394 72409019 72382876 72742400 72885245 73586500 74177796 74130495 74575251 75156092 75836419 76123174 76540081 76596557 77133825 77685675 77907368 77842995 78703223 78903188 79556957 79543746 80337524 80550909 81363399 82042973 81969627 82114966 82242293 82669888 83088227 83445218 84111749 84209335 84221205 84760248 85438125 86025251 85932176 86323268 86495028 87079290 87018246 87537604 87629559 87642374 88412159 88666639 89438504 89501604 89761749 90160970 90528523 90698183 91485815 91961010 92624505 92935476 93115687 93431893 93685724 93831299 94492475 94834072 95566520 95746852 95927328 96089203 96350561 97105303 97756754 98427952 98569789 98695090 99095140 99775407 100651915 101250206 102118973 102542563 103025242 103246809 103916568 104383957 105054031 105189108 105861058 105922463 106768995 107588245 108005727 107911858 108072355 108289719 108428710 109158098 109271408 110003430 110372897 110610325 111326396 112045444 111951982 112677543 112953618 113000262 113757951 114147975 114227085 114751413 115059932 115834057 116365534 116685232 117315038 118105365 118203658 118798248 118813173 119171558 119650280 119730594 120035235 120046924 120557543 121305465 122205439 122150315 122431687 123218137 123594803 123680953 123680859 124008581 123991743 124292932 124694286 125240338 125305523 125308073 125638170 125883625 126344120 126943006 127011090 127593097 128263111 128509160 129273624 129663745 129851055 129903653 130547815 130615098 130538580 131365764 131557387 132322347 132900522 133793926 134366050 134519265 134960764 135448389 136028387 136381120 136830570 137489452 137545238 137880443 138285349 138680762 138749847 138933085 138956853 138984004 139515864 140176004 140987444 141339825 141644061 142265250 143088017 143099132 143362622 144012986 144854669 145473908 146346983 146622567 146910016 147455742 148110299 148205912 148403797 148395794 148936557 149058638 149576458 150153850 150406661 151176348 151810224 152540886 153342112 154167342 154181808 155020826 155541519 155806210 155882180 155928973 156501878 156697447 156831673 157364555 158238863 159041286 159832308 160217988 160239461 160459158 161088233 161349370 161831512 161801060 161757539 162037829 162233373 162258771 162239170 162491730 163376511 163910042 164552505 164887328 165558168 166216512 166670157 167352770 168214425 168229347 168418968 169041887 169149703 169231798 169855307 169957812 170289466 171137213 171405734 171410512 171552031 171631954 172479489 172489174 173015543 173633379 174175622 174789246 175123157 175251825 175334132 176212884 176927140 177554963 178072670 178218807 178500254 178959728 178869225 179299482 180065237 180135048 180499921 181360326 181867373 182345322 182269731 182960405 183198943 183859966 184417732 185023225 184986104 185591614 186458473 186959283 187635224 188354165 188811805 188807004 188814259 189542726 190000190 190236191 191028243 191633831 192488639 192399291 193242002 193346271 193519909 193447492 193638243 194106959 194310094 194520803 195086410 195344679 195271526 195540050 196186784 196337133 196399856 196979744 197871632 197991353 198048962 198371122 198450523 198631354 198579464 199040959
1000000000
9999
439 1000000000
701 946958
766 348541848
998 148847644
491 1000000000
377 237161296
269 120579444
893 225142252
838 146748023
900 288642095
573 1000000000
557 266420769
610 26856390
816 182003358
765 92970332
77 62829426
718 116076688
116 447904691
541 444195379
590 676814104
723 1000000000
73 228896161
838 139425121
806 177793760
727 709431310
830 115471499
743 164610136
487 32752916
796 680439460
74 87266507
152 211457631
248 251113222
201 194772075
688 112581056
105 252295008
457 169357466
118 44781165
445 251997770
962 107468200
475 1000000000
44 232421342
379 156673220
932 669099769
869 323681617
26 828066441
329 24897814
710 68662203
383 372647383
632 1000000000
895 1000000000
760 1000000000
201 146390942
558 31615425
173 81960288
267 13452965
404 155682726
701 9367978
428 500879987
37 216632216
558 123607395
436 1000000000
699 10815020
88 1000000000
73 435282504
243 451734241
322 23349138
260 61924795
597 233801627
682 159533490
26 130174348
55 86774498
752 50678118
58 14470517
41 85357570
387 118113084
804 109546979
402 272383050
737 801621654
287 70115646
64 186148522
450 204150794
929 378569968
595 11339698
876 49581785
658 61964302
962 36273148
816 3505702
889 1000000000
163 589031470
986 45178856
844 253599523
846 480542782
508 5666829
627 85289571
281 104572383
179 496309551
581 69466004
156 523677459
55 337454516
368 1000000000
438 71353351
470 290292826
164 382100966
950 187581112
40 2627474
744 54106014
730 233050861
580 197173141
570 200100438
58 462858173
384 656622078
138 325839058
860 713383677
340 450943613
350 73369130
200 444907962
294 621059312
486 27822076
709 146799179
598 1000000000
601 309136447
513 78731403
563 307279477
381 181548082
196 391468948
988 140196409
930 243273591
228 1000000000
663 140077376
567 316155575
993 488984704
924 64216167
450 177137886
426 68689208
641 741968511
235 977003
486 61594916
654 267775876
577 249646620
963 174341289
778 66688077
698 319921699
345 1000000000
259 5392019
366 594899444
350 88676191
657 56960040
571 250676110
138 35222518
651 187547935
577 160809680
948 216690236
935 142163659
655 102769669
106 185948046
461 545633060
980 410579346
44 149718262
491 1000000000
6 51684085
153 1000000000
801 747831744
612 72212894
767 149427658
118 476159787
351 388359796
86 1000000000
633 652162641
548 293415328
612 418072973
296 12697054
498 101243433
810 334195142
690 119463068
922 52093832
868 548408591
256 45577098
937 229607566
300 17665587
735 2090243
246 239479179
247 178724571
150 25035223
145 152022333
13 339454136
926 306399063
513 5350596
212 215652347
836 151315252
637 45716566
636 377461865
167 200138224
51 164343130
420 195458022
319 7938307
626 32227878
66 37629580
291 406919637
75 501752782
198 373731556
586 71386304
451 118322883
127 843401942
626 308813347
962 345161499
859 7265304
731 129777301
286 389378529
258 56321764
283 347449006
623 325054611
714 200072554
954 85314043
131 241069423
219 243616928
119 6351547
547 23424932
836 26060179
384 160814332
723 98170693
259 465725977
693 164891569
917 628030360
249 1000000000
461 12058497
438 187942444
298 510664667
374 7604097
710 363895250
168 320079644
200 41293902
667 418228658
176 52469005
761 48285453
37 2832087
953 4053492
153 77337155
211 245112987
891 1000000000
367 107622633
68 106602353
749 66725324
442 222243108
526 8442778
958 13886676
744 14388709
128 6888150
364 146159968
265 33720434
786 1000000000
39 185069787
299 49024640
883 204249876
189 14577687
430 18229400
802 8104253
167 166474764
409 153050026
285 14725466
793 129170328
570 54898277
292 149389451
389 1000000000
329 3314122
941 503815596
808 1000000000
524 260648727
873 5060780
593 52793196
52 670242180
852 716035156
977 194110457
645 25942093
824 46571157
877 9399439
313 92856392
730 131130315
748 37258123
861 123028036
122 76649599
670 1000000000
721 1000000000
494 159368812
26 383734886
579 5307971
662 168015130
911 448680663
355 125035467
648 50972712
299 135927494
160 67982941
189 413277
14 200613956
216 19501574
82 68517041
422 125503411
923 91144018
78 81173646
515 452210706
88 16217324
697 1000000000
292 658539375
333 274744138
498 608912100
15 56897632
690 435709621
520 1000000000
324 328032743
150 136516293
505 222605308
954 31777970
311 29038343
820 4359352
271 250227464
477 5755170
546 114825652
803 4106645
54 134403707
576 458691344
349 175002163
946 154583109
725 479634901
275 1429339
216 289295594
850 135490421
589 427805690
838 2068266
340 765559711
889 115835613
725 610023314
394 239543392
767 31059853
217 925503101
556 143151772
350 51618019
643 87123763
225 251033923
613 224035950
426 1000000000
280 11439241
834 46659384
557 220949625
463 40629810
884 175851767
770 167278755
950 792136229
244 109029164
65 27544438
787 59900082
103 202452508
425 322934819
766 24996781
428 255559789
56 64968062
838 7156389
259 171889516
830 6089987
593 290268900
483 8506809
673 14837047
455 23631794
19 78874930
369 2126885
943 289781924
969 561275382
437 172992160
735 499683704
133 115476699
219 901060571
295 21518718
181 258092034
51 526152349
614 279893990
497 402267137
228 1000000000
138 536228463
88 290314264
596 568601561
731 155169370
769 1000000000
283 300922910
727 266031390
954 26746464
856 2888543
126 58341571
322 474355749
313 865009
423 181422430
466 153318184
574 66753655
24 1000000000
182 22257652
813 22850879
689 757401279
464 139474696
278 1711219
89 132659173
869 811217088
464 54412938
190 1000000000
869 19229764
617 298383259
256 147650437
519 373131981
41 6171661
686 331866266
825 162433077
527 13560464
6 13392802
203 178126064
233 209563983
456 156130615
347 386050633
679 401047302
186 54559111
241 1000000000
200 671501643
349 3539947
700 188498518
10 116212398
277 161878498
90 356746208
429 246503224
692 368731
19 123813823
440 17411506
615 9104541
262 49531882
937 56019418
982 43398776
481 496735728
544 328184998
671 159466316
700 221660342
811 69146931
426 561389225
61 87963983
610 139509686
166 219193425
661 741119701
996 20503714
873 252284504
592 1000000000
623 135732888
659 542537537
24 209687988
99 3071166
570 57769119
18 126192491
759 95385936
303 250746728
670 20697856
809 71675523
118 226538819
858 274215600
17 195529793
57 1000000000
166 64768692
214 519569550
621 1976930
1 37218924
86 100986308
386 120111586
761 1205264
65 69456520
902 119262059
422 1000000000
245 965465680
425 421639075
423 136574262
195 10705322
242 50159022
674 874732
503 66760689
751 277598842
775 41134487
995 189235604
680 40088039
812 548859371
396 260390214
12 319482576
665 161591145
50 188414005
969 84417391
845 29432266
555 208292829
943 246045852
359 43791924
983 383413762
925 292009430
861 377801698
117 267206905
585 1000000000
622 81410483
459 146997018
243 110419071
459 99758806
817 70132517
305 276325088
801 19508636
901 945769347
691 37660482
527 819306317
423 15150617
784 30557490
382 107686800
102 1000000000
390 554484707
531 1000000000
489 205249919
93 1000000000
837 81908322
670 10509415
804 20026649
60 164453082
325 58657722
41 1000000000
663 362089141
36 1000000000
500 567317582
725 362191937
811 377035177
540 84735968
892 178263900
609 7321874
335 63588706
4 153895233
132 126451342
661 17762017
123 53594759
180 86363714
228 3917269
897 99049099
256 309543137
564 156138804
629 37919623
6 27572231
300 61603711
133 219381419
862 326861318
483 568502675
193 918945650
830 462104350
855 339743405
928 21011969
110 11468345
511 1000000000
656 844750272
205 43171968
188 1000000000
361 6676721
530 479913140
139 303004567
937 72909858
203 1000000000
179 300943966
329 1000000000
615 793720328
117 187894588
301 332955827
879 285283155
782 1334080
783 90770416
280 57295888
461 210313743
900 159805852
137 114733083
722 24790288
68 21638611
739 123673906
76 268304563
989 322628572
659 18214526
706 134796775
71 188987379
784 45032975
178 202982002
97 38276738
586 1000000000
659 66487588
625 82339745
640 491963403
982 428121304
287 815577
881 320248399
144 74036068
42 209509634
403 1000000000
320 1000000000
672 16073551
230 318461340
959 49060329
489 1000000000
200 463413874
458 1801866
843 1000000000
57 113760053
552 77515082
510 197799759
272 155995439
602 97336405
393 57138373
611 37695824
444 1000000000
226 5771368
986 706073335
880 926287020
274 187932862
12 24698553
987 73704926
245 454305280
311 103033870
125 1000000000
245 31005943
299 8344601
940 49599883
359 207579543
462 946755522
456 1000000000
810 54591647
432 2615722
344 262670785
862 1000000000
384 26308242
875 253740113
930 79334
749 210167052
455 129134728
229 25434342
245 82993429
611 83747001
229 109055490
439 341629906
87 1000000000
714 4739346
268 255833269
346 133110907
962 153130264
369 108747970
643 123360793
525 42217335
606 204952126
160 613891449
410 219731308
481 356110329
441 123390459
600 10163803
514 73048896
340 256351604
693 45987161
511 159675193
562 104664127
40 196779556
337 165028175
879 875738935
282 443775231
340 2989725
853 129899299
16 913835792
802 242762592
473 1000000000
225 1000000000
976 1014049
266 2286148
733 128428474
814 768927820
1 166574651
995 162105092
514 110406719
667 153914920
138 336023579
476 127868121
743 159190351
568 237303325
179 687940560
398 79221645
829 506594270
285 47420036
677 12746620
503 128215162
130 161586538
35 77522698
758 9974528
713 1000000000
128 31523573
433 83445665
336 287337242
379 24663410
534 295351316
495 179358479
106 130057769
21 810083
885 110928637
942 506459509
573 263506432
712 336799192
179 59811936
44 48310181
648 192963386
99 1000000000
250 737676758
939 136392847
819 174890221
518 99778902
833 377764678
66 285127528
646 239516190
817 749316048
521 9847356
106 251267236
937 404629744
997 277501402
80 241704543
521 344577275
125 1000000000
256 88270083
488 691000797
329 40487461
641 90021359
276 959025821
264 326790574
490 492979798
389 2958885
73 63140670
25 426978688
506 102377427
178 30352058
333 16352128
441 77800869
699 133256552
15 1000000000
882 204951125
402 1000000000
252 23241994
492 985854913
471 233199013
563 297128944
189 39743032
25 47917119
988 1000000000
701 131321565
910 2303253
790 159874362
82 40948432
822 166351359
72 154321447
436 3967201
392 458075903
176 133368017
426 1000000000
42 14922236
662 109250783
378 2622532
188 178641999
936 228463097
236 61697759
413 114798096
406 190005668
471 1000000000
259 22205702
503 670191824
841 1000000000
398 38448052
778 13072764
50 109774165
412 19912907
541 1000000000
657 106644603
293 484036498
791 1000000000
316 16908618
576 843959078
480 1000000000
811 18692813
515 333324156
831 53472531
220 31609110
846 65810794
323 253288272
631 98143598
152 50657614
834 214684283
731 14748804
295 579785225
356 660411161
390 743035
675 72340179
64 1000000000
696 1000000000
827 11737256
948 54355826
920 137658839
829 1000000000
848 152227491
156 1000000000
561 129974176
722 158707258
724 249107757
517 28714286
282 1000000000
175 238132779
890 170489776
23 7294305
323 162853097
228 177374940
87 184173137
592 1000000000
541 189742898
738 73082664
765 468681844
474 164449176
335 16222300
456 1000000000
771 2920333
940 71811665
401 28277669
966 14593342
841 972406521
342 362118119
395 11736685
884 71693264
263 304375131
577 255315513
334 304080254
515 464162594
78 549907666
163 455705
152 280489955
2 175306305
325 14699740
950 103906693
331 290618455
337 82155746
332 29114762
866 30212437
935 31478568
600 343223661
35 73341173
997 187957423
106 7105645
168 50912079
467 16166920
521 91578000
918 22875999
840 780834695
619 165311317
749 138198261
666 74452721
904 159595134
11 22358630
457 7014679
406 184663330
920 543416404
900 174211719
390 64923603
291 54155509
633 214902532
812 9082338
138 30420693
832 122714486
194 277930632
725 136450755
591 6437611
613 39918643
987 294898055
310 260423925
293 105923625
850 345997032
12 3291022
728 15712895
602 10791667
792 122733976
462 80850873
642 69386504
32 234652032
317 319880744
992 119397744
883 531783416
342 359000829
404 54099633
282 1000000000
670 15450472
708 66042357
58 63393165
676 4319305
176 36924327
778 253145826
192 385224588
383 177098829
107 236528256
9 644797869
591 315657735
90 115665271
934 233344480
520 154323281
398 82127348
645 168532489
489 85962214
839 640095186
878 97668443
952 265286184
484 85859601
343 4945173
877 347976587
28 18812673
992 1000000000
623 103447460
37 231605512
616 460396421
964 19812128
31 33365205
341 224693557
780 179465228
280 13320693
167 4884827
205 192721826
640 151160644
860 407201325
583 554379163
934 222634018
493 217740089
769 1000000000
832 46708040
927 228016736
978 48753846
526 107302200
57 37973030
168 559930414
23 421999564
571 757648009
722 144683546
961 33706607
820 98208237
257 296022314
284 119650493
842 1000000000
730 235816291
126 258069405
198 298000243
420 127231594
960 810504
620 657113361
352 597326496
374 54992854
78 4595803
778 1000000000
794 158490726
73 94379388
156 1000000000
529 34473101
652 287873717
683 29496437
363 151454153
280 491126698
247 10914540
478 335501694
201 1000000000
967 118044249
354 1000000000
817 24035307
929 211928605
862 116732203
285 136042292
684 76902993
192 47255758
829 1000000000
209 1000000000
648 67570359
824 365816782
405 189458266
636 1000000000
612 173298018
231 460827420
637 140735501
424 1000000000
344 59747114
200 1000000000
221 99748733
613 203655570
868 161265516
920 205615985
925 131936312
985 579514434
913 15575027
209 516637045
478 38545995
806 62845689
685 73194615
841 50504424
695 23000710
139 1000000000
26 1000000000
803 25335352
776 109753911
104 107565300
232 139760138
484 105762973
882 143114588
30 222585794
773 174631425
630 468567657
547 7985917
715 376192394
163 271271709
735 221712762
853 112343
225 108450099
817 413496662
457 58459442
55 17383111
928 75754742
671 221891986
124 44920479
578 119887547
342 649776247
150 29236222
150 362668897
756 1000000000
397 196483291
997 94306220
993 214069417
607 838846899
628 348338290
676 147693475
628 184094802
939 1000000000
27 151326833
235 15364552
656 129254759
118 1000000000
291 118688578
459 567955101
939 86262912
42 1000000000
370 432819136
667 107480752
295 320072212
102 360636794
10 77665841
91 208630896
59 185289883
50 247370063
107 11592869
539 894351962
128 183455536
790 1000000000
587 278422340
891 25794911
292 58550125
555 34362274
924 1000000000
524 193615417
825 39107390
944 247294611
701 1453406
237 763461830
270 28924345
597 207555650
398 43944413
663 53847592
548 228455855
514 45508196
327 250333875
776 3211709
849 27538111
752 162982280
185 72173645
682 56780758
551 42576669
222 409129232
987 11799484
428 225807390
773 36049206
60 37663357
437 84736656
478 193258763
900 8818182
723 307631566
984 146529629
9 347235115
890 77686582
857 118697815
595 99849627
860 117388858
985 128663976
104 1000000000
534 281144507
359 172655356
656 156780338
871 34829778
9 409214025
506 333927129
504 279436719
255 181168795
500 73524591
318 1000000000
455 195249720
574 77597567
1000 22417378
305 161758614
39 147560924
630 10308057
172 225007136
341 262476048
295 164313537
351 787950883
648 140721266
138 83815108
880 287900379
543 142444501
413 1000000000
806 769253004
960 1000000000
680 1000000000
962 44494440
43 123626837
89 692421045
1 59896357
879 69217843
168 213999565
258 365127684
602 51090971
268 697172221
837 1000000000
732 14963737
163 402052348
641 10907492
451 455324623
5 396630693
309 461412927
575 56913831
641 330463284
583 90517856
591 298161469
629 399191209
823 126396227
393 175677456
241 880520735
635 1000000000
725 231708414
892 105786325
283 176528838
722 149049472
452 141636602
294 420011660
726 75685502
601 649213484
842 12789243
937 73384714
393 175878959
576 339978717
154 88136122
500 57867915
572 13338127
583 1000000000
881 4604647
583 288754831
952 415014992
806 89381737
96 21647057
11 624692610
155 150763758
126 103984582
776 167065486
495 8050453
751 42582627
246 10533568
696 55172873
411 692717681
411 7291378
54 25815288
321 117238142
295 1000000000
856 757397706
487 14191661
833 488937150
988 1000000000
508 181116246
383 117212113
346 93595041
313 823808385
449 159050519
696 36498403
827 5869547
694 719893520
447 281264833
330 137600043
628 432929696
171 148165708
812 271454140
723 16972395
342 51883935
529 1000000000
146 134628714
469 129135013
576 28623970
871 260732074
712 16424469
663 255312102
42 71765330
101 1155990
262 243910134
25 26102656
188 108971401
107 224810931
316 319666395
996 89213141
295 10785911
674 64887514
947 241812375
238 560129280
969 333940427
217 893372435
10 39868568
201 771580696
220 736735764
512 457410585
49 235584767
989 1000000000
664 53276733
359 568788046
752 52258176
648 24007384
891 218532966
783 73073281
200 20454516
676 771106215
407 213423876
695 74897723
776 15501777
368 411928585
243 53170869
335 220259216
264 65659546
36 19820907
727 16710095
15 726776227
977 86720362
425 121222112
692 227170447
240 24281022
641 1000000000
221 1000000000
265 404573804
673 38468045
954 303002760
754 820917782
462 19029393
970 134844186
803 345833483
439 56210294
443 283408072
267 445608463
365 81582962
37 729882900
625 36464783
733 465629300
151 196916
195 20852394
190 926387105
591 11973214
920 53609698
921 133816545
692 555449495
177 188495457
891 16945398
543 277355145
27 128683980
571 538961698
717 117555465
117 185677792
97 54613204
878 258782728
968 50824406
116 537201548
216 35330174
409 21395555
707 432025579
11 286564485
623 213704823
708 48738032
54 184299057
226 922204327
615 123829164
911 76753062
913 299169901
66 19678383
758 24752865
627 349239912
765 151930378
138 20510734
110 553091106
967 1000000000
921 127924407
490 194787388
574 115743491
691 1000000000
637 4322520
26 1000000000
78 125108463
719 262971482
721 314348542
130 157434383
119 327340075
52 240389734
326 15859049
411 120975450
648 403091643
153 66674252
227 351104390
372 115668942
305 464479189
782 49594687
504 2035173
37 122563070
226 46558212
835 635732
806 168219180
839 16283162
539 2052911
545 1000000000
739 94158126
161 5125804
293 24167063
135 112337761
505 1000000000
867 23572155
655 91322723
29 59007326
143 48865789
125 157653111
466 131095768
403 1000000000
214 72976274
783 85985573
780 22638817
234 95176206
845 153375987
850 74881901
591 243274317
968 15093421
411 29756957
645 464167410
218 35662307
16 61083520
859 130167238
416 847861433
5 127336423
375 511242392
210 23080487
740 161430929
457 1000000000
871 589865099
418 530232747
303 171216435
333 16112354
686 115496263
738 109831314
147 17179940
209 73755325
463 17753339
330 89770124
296 51710519
125 125513244
199 151901365
482 16740452
788 12525933
58 219691404
216 263443097
227 167827833
321 6867322
78 437731810
544 238300879
636 33733237
758 172595831
635 177556506
201 30522824
189 104770954
339 339088060
17 509540540
515 530146711
102 278840674
553 355486457
334 101954352
4 16386617
176 56551135
982 35536739
604 124669026
374 90833093
882 375020677
44 137990642
922 5190519
376 36251733
532 1476724
331 244485917
320 117064154
795 1000000000
159 131570161
497 21244869
639 3297257
405 94130751
577 1000000000
728 282861952
486 413164425
384 879509851
52 1000000000
183 9909917
37 7567269
323 195968973
423 32682130
422 489394925
100 40938673
183 48981577
587 21510456
678 149834489
956 37139338
626 1000000000
583 42555222
301 1000000000
484 244909630
430 321346985
315 264615894
653 234227220
212 827386298
74 7412038
71 229468952
190 338634702
660 19641249
527 972666505
819 31647082
550 237615212
996 3838503
11 889426527
776 39096
575 95930858
205 118680740
904 68676999
373 344152502
448 65234070
646 252909
429 18122914
386 73979273
233 43775338
648 123399375
915 94816377
103 151021750
690 733860133
809 166266634
424 811294310
365 199974769
668 70975565
219 377082915
158 221267427
259 5314866
510 1000000000
189 222284640
812 59980954
369 152376643
976 275398256
503 167211390
203 554839174
72 1067093
251 516628676
66 390523580
281 440871526
294 1000000000
718 1000000000
293 428292
760 26485028
981 20932269
577 108804453
488 619758
63 76555958
972 12602245
100 146292968
427 2354343
495 264105787
868 65044691
151 67565954
295 295165987
134 112898973
683 199754112
547 243647961
986 119079767
502 169947771
907 177665474
607 501357516
246 1000000000
318 184648477
172 21713298
715 37926651
355 306886832
39 387761614
524 1000000000
696 252315947
911 895061470
759 10358619
893 389058484
909 1000000000
4 586081834
992 202463896
718 1000000000
762 4451999
769 434174327
241 505419964
519 761378074
647 305378161
854 582699172
219 12101089
568 210478639
172 49118556
772 29173465
996 781819144
914 1000000000
930 47650797
418 31264686
310 148329673
852 156656302
368 129680943
200 39166291
88 15195950
694 19776337
662 356547536
694 82573165
738 1000000000
824 155944834
253 180311836
453 513399831
981 481327153
819 124874108
899 287512496
371 1000000000
120 138961964
70 1000000000
882 1000000000
771 37281352
795 111731986
657 87521079
66 538076172
474 49931514
774 33213246
677 25447516
969 243299811
745 31807769
474 425565338
896 419673
297 238017410
273 140908038
702 140460802
940 1000000000
897 605733756
121 531666894
42 84578885
560 264937901
913 214648435
682 56594203
470 7806747
845 476341643
226 61001039
178 538768965
483 130657471
1 1000000000
634 1000000000
299 239715319
8 1000000000
382 261368207
203 164652746
44 87728195
645 1000000000
604 35520639
629 76959902
509 58275767
314 267351296
129 40832984
174 75065591
39 331774437
112 418081094
223 161342616
432 614452001
297 64887196
358 288331333
645 114287639
602 179261669
43 247073381
732 408430401
627 507573624
780 52891280
677 80326934
546 336086776
233 54707165
23 11278778
583 531754021
481 8470863
376 600095440
689 229634989
690 84149191
80 139992948
831 21419443
724 93696815
485 233832160
271 127280774
486 4393022
120 32234224
33 449319309
670 1000000000
981 315093908
75 1000000000
124 260089375
254 105293095
461 1000000000
207 1000000000
848 60413348
574 718740243
109 478198440
747 118029425
108 91315101
790 4102344
565 7296483
719 76846616
312 943787368
254 57994096
62 311176043
987 588545038
29 561718245
343 45704556
782 142272237
272 402603375
522 58652852
568 36224711
335 2458253
565 176707508
103 227210844
601 6105933
936 44814452
482 5496452
308 20504235
498 42076996
42 10338259
280 213973905
266 691852172
532 122436827
675 608255231
654 1000000000
567 41513375
326 16595116
45 49526675
948 213782135
469 32217525
616 607707408
72 55184815
714 56009420
956 93895457
802 85890347
722 595004510
88 10140310
58 336730532
445 123882247
213 769293202
639 63935041
1 115746804
64 200080275
640 307753733
990 9429701
408 602689201
667 59500913
963 395277737
525 112644917
151 206734974
78 489327744
286 296637
845 593089504
975 42199853
410 970034013
170 752952785
741 21668769
583 57223153
294 179487183
262 539231828
997 142448538
631 1000000000
130 344496336
890 56123818
533 235913357
199 401380521
310 347886786
174 68586534
389 33306862
320 24927354
635 34063735
643 180530993
958 2161909
217 491370442
168 325227353
752 100175199
215 41945895
434 109816153
365 9711459
141 225802964
576 471343749
379 26425677
66 36479054
691 75727778
394 166136349
948 51391148
120 29061660
728 1000000000
580 41469852
254 392120688
645 42499019
102 1000000000
718 9567229
416 101379386
780 146427750
748 1000000000
464 393085749
979 14441212
506 1000000000
691 436812530
50 127282347
133 130952420
817 1000000000
466 112449652
541 48023342
584 105010416
903 112995032
616 888904402
584 123674535
443 1000000000
583 586967098
568 109184480
963 1000000000
390 57610882
790 150153569
247 516827072
815 268453
666 566297965
446 336234458
951 65522936
418 388396472
438 76618549
901 71511819
175 734444584
958 890060680
506 24250529
678 3308960
903 21439614
843 329464878
422 26555839
254 139333298
999 503347253
455 43474684
571 348686583
342 13825877
480 40656
124 15380019
415 96634223
87 88681274
289 539468354
537 47862187
236 1270707
768 499871099
298 4444286
14 192983409
522 103402492
426 103704888
507 392227303
260 440847848
751 13088683
931 588467183
781 83727901
57 55922605
573 9830124
525 885097292
47 77987904
911 55640114
203 27412615
591 1000000000
985 33319482
310 152479998
849 246063419
642 86368814
92 147505144
452 122851980
64 6471402
956 23102604
390 290483115
555 766573566
15 46119803
359 549238960
921 242656889
586 189437712
550 214511214
42 58253879
900 450441879
433 74792759
749 64227568
374 246238521
112 1000000000
361 98569188
797 15566312
849 108032824
452 103116930
864 137392270
876 28165277
861 988920366
927 66985610
504 12101662
541 151603100
641 144297227
788 328474618
328 166244515
149 331071203
190 109584842
712 613635860
193 43688036
469 41345311
370 3102022
133 344004704
250 1000000000
358 412448787
831 638996342
794 1000000000
483 196823788
95 512749188
804 13180846
639 522541564
532 264142659
761 122837436
922 0
652 272453709
141 3836509
698 20440874
71 144490281
634 98416945
95 117865168
364 330875186
773 227659701
896 180143989
745 142112920
678 16711102
803 220362305
270 82486986
595 455251667
184 1000000000
410 20293231
836 1000000000
854 486898067
587 242171342
280 1000000000
67 444211258
841 34331849
686 176687035
487 404431119
34 941303304
292 94091471
473 157710013
246 206972737
641 3346672
655 456818030
404 152918508
998 410292214
585 7943814
2 48204989
904 1006773
125 22451923
664 624364
406 510709318
659 112635439
677 180571500
776 46954728
850 8880799
207 29731925
605 60195436
1000 596681281
958 220110622
756 19279068
510 697557123
505 1657344
587 235290267
968 280111002
646 41582840
298 33200302
192 66728804
493 548362893
791 490586914
331 25488770
573 128709333
506 6888584
736 21621625
356 1000000000
306 1000000000
911 41648718
329 196232189
877 28832244
119 104889804
509 1000000000
987 1000000000
575 482362222
701 177226332
659 1000000000
533 46936434
465 1000000000
819 10685923
505 1000000000
247 74621170
259 431078277
257 505111622
7 27730828
65 40127811
253 169584012
24 29308619
606 26855126
676 498713008
488 255469547
326 1000000000
284 978820116
199 814855330
899 525500321
189 39219460
555 443725219
946 422646785
798 1000000000
117 7724611
691 171239082
741 787218372
242 171626115
972 124331060
154 80823996
817 1000000000
53 28115256
668 20084991
610 92853838
125 1000000000
953 127243330
636 1066185
66 1000000000
153 147477116
661 533719684
652 356907583
226 162632429
61 144637890
266 43737044
581 182553980
611 413950963
786 83125824
462 41561858
605 317900580
732 18939233
23 249485894
427 406306472
526 421491834
221 13726411
932 1000000000
537 75574041
936 94198524
662 515614653
265 1000000000
950 72690204
489 215683534
872 434886136
111 455826586
548 624323536
947 82502655
730 224667001
389 219233095
762 258483026
125 1000000000
996 53034147
715 36902733
224 441217696
311 165694341
318 114411015
401 58486672
574 339501524
10 2000555
64 759902734
880 5367762
421 812001796
724 309438625
611 1000000000
935 25105164
84 167493412
527 66775718
134 18589813
294 432896257
755 130990776
531 159407813
282 16274333
573 130488506
554 156572006
678 382051581
5 323097914
253 84199130
418 69010352
842 53707004
145 235414680
229 310519889
482 16560300
326 653084412
341 863260136
429 265405985
42 1886321
586 96078489
801 350574970
541 42062914
3 755243791
950 756825335
214 4200882
990 65726803
419 150503311
203 95230690
611 33895550
343 28736467
220 312109221
576 34047071
96 501153
824 39966364
277 48154433
477 583299705
765 591835571
601 386172028
607 11589945
851 152067351
731 612489904
651 211808758
768 457722773
665 1000000000
256 366062589
669 25221427
634 15123037
47 203014018
942 139754747
927 51815849
205 218346022
69 343031908
837 1000000000
449 36629376
591 23564732
947 105321194
779 349591784
556 404720127
402 595673281
170 45079922
378 468395442
199 188602132
413 81477682
97 108748893
153 79963723
258 22256271
336 59740646
432 127107995
32 264185401
365 346510897
3 17888655
952 23323195
488 56981554
185 488385871
271 152646371
200 48818592
824 1000000000
917 1000000000
843 148649278
880 173524317
448 60853491
561 1000000000
31 106442185
344 51287532
208 413565163
565 272105686
27 8635370
880 159937983
793 209356033
746 20508549
232 487440676
929 59279724
609 691569545
486 245143403
301 402031891
954 46801044
883 8380058
604 242427053
738 15154254
595 14280505
980 279838221
865 216190268
432 1000000000
461 608708774
557 493046697
703 1485387
13 59252948
494 30588431
399 559106953
452 40968954
603 730834615
752 72856138
521 216115729
3 18507266
73 708827019
707 97363890
892 383993871
9 343721960
176 5289233
749 25346403
846 261239018
48 132368227
286 165153751
288 254668438
169 164921504
614 172969326
397 46665616
499 102527405
132 173711811
958 40469004
861 352803261
678 1000000000
215 5546982
717 1000000000
764 151296900
570 34496737
355 35018853
636 298082317
540 107607781
765 169767488
7 173611575
644 173464949
276 214870764
481 19665738
467 121429863
324 1000000000
108 50020331
702 353420603
775 9480920
925 6419488
404 60898755
18 73037835
348 164719312
229 101200967
749 29558473
831 118627849
720 704297048
78 159845454
622 407419567
740 136869160
205 51518286
263 480181713
231 113356693
905 520047122
483 135529107
441 153307955
48 141375386
975 1000000000
816 109235878
450 184432027
730 125496573
500 275218
46 60043004
108 276710827
460 195968422
218 172852498
212 44018220
358 53451218
782 315358745
769 292756104
66 831335760
201 1000000000
753 305830884
223 868281
449 70281324
843 36374615
827 292910229
174 246639770
8 51971737
302 235392127
654 1000000000
125 7754676
863 19802396
425 136473805
889 189350647
100 160207527
902 68808885
765 802280235
397 1000000000
267 1000000000
814 122599485
56 337329412
233 120155697
235 280191879
933 1138604
116 59343389
364 127429348
803 23811725
678 924387477
472 749197895
609 164089422
931 12013192
222 51776540
13 75836862
357 55225932
252 188156013
390 55935105
569 56109736
202 962021748
877 17438356
543 117909953
942 1000000000
743 28433275
422 596183194
696 33261405
187 12843741
700 486030544
935 678355695
778 392831588
809 468866604
665 662287432
216 657197417
955 391498674
70 643660860
191 460473620
802 14578517
469 226954144
292 1000000000
501 13910508
348 437145270
351 1000000000
522 91201146
867 858707623
358 104889768
57 2943934
705 403596316
753 22192512
641 54569582
916 84036115
943 139084152
536 741474465
300 332783018
543 588370514
766 1000000000
855 291171303
191 36253193
122 17078934
941 26948316
102 6110926
490 478889004
141 133263070
165 4042706
62 211901516
173 297960334
832 39794234
796 329446770
813 256770041
945 40936660
860 1000000000
756 727942650
341 375483997
661 473838665
864 369169962
148 376225871
669 405315042
169 87463407
149 410420563
988 199446095
934 103931585
646 213602317
345 6283688
605 71996238
903 128723961
315 4008837
774 628273124
462 698165826
407 195714939
775 1536292
203 369277452
87 93704570
185 184536361
973 26256970
792 9811364
976 615339809
610 79115239
450 857605730
206 11325600
10 65180107
468 191021931
16 3868548
52 264061141
780 1000000000
958 85082707
918 370807110
210 448843106
366 175342815
328 29500462
844 17341152
824 1000000000
480 173572848
314 2620934
179 71443999
223 330745496
947 415788277
197 41689056
953 225017334
957 53070195
462 91703238
392 75226621
256 521562583
380 57188447
105 33559265
75 18742021
24 425208657
804 103487210
652 74657696
190 339593288
279 99925753
899 5854530
784 144634763
154 1000000000
359 67445354
83 125416897
980 47924877
990 333564601
943 4133419
795 29411630
144 109863228
10 298653409
359 1000000000
907 6016701
740 171136218
351 102058108
304 245782991
508 521953739
89 243790787
491 152197904
704 262464555
125 518792797
190 66846949
648 135282924
553 143882284
390 531622867
931 3149152
557 83386271
755 259109807
831 884462741
736 728991440
739 168455951
556 858944296
857 54843249
118 300670200
881 1000000000
990 412549408
595 593231442
620 533799015
839 1000000000
584 245531266
141 375077246
34 20552810
77 19255212
490 159610767
527 79281250
472 726684670
763 66693191
709 11496592
497 447196821
207 190021877
42 204011344
503 57434224
332 464414722
958 27655192
865 1000000000
898 58008093
55 61983289
869 230637452
848 77295011
181 634635668
339 11965487
500 139308584
303 117583026
281 260496473
118 22870303
340 1000000000
199 123314450
325 203889496
946 13011574
436 236699001
263 183079661
553 1000000000
22 90407416
76 1000000000
999 1000000000
741 8059621
154 1032088
108 724132398
408 1000000000
169 26563298
743 51394838
781 89067681
688 58745626
878 55672643
716 1142871
758 93069426
217 73932292
907 157763849
737 39451188
87 14535604
402 201933989
664 135503174
542 23275028
40 163822878
572 27060857
470 318459635
996 387231185
690 12479884
949 200609943
596 105040917
921 155301492
484 92059868
47 89110564
218 80036003
31 303238584
694 47952902
562 391646460
248 437117078
614 99918057
688 165105685
508 1000000000
910 1000000000
28 35652501
307 15510594
215 136361433
741 144278999
811 61284944
566 57243150
666 15373976
548 16227155
658 236873950
833 597187955
853 5343455
299 46129700
377 26061872
756 207497028
224 242306860
627 160693365
889 849512706
592 136286376
948 279366363
291 129035107
929 273845864
780 580479
512 193650539
571 1000000000
777 219600894
984 161076601
556 74459096
467 51501757
145 472093551
892 280135719
808 102703872
707 265294428
514 13563875
177 53553358
821 68437846
652 53528329
762 139483096
117 55011899
202 839347187
861 178625564
908 131993666
219 889335777
223 434488064
190 292508440
421 93063357
384 116761726
541 27061285
576 80021031
814 90918705
422 555740878
994 74768887
625 208191082
928 121630463
579 471177536
144 60724628
75 35463442
130 122333125
426 303895947
902 218904327
318 1000000000
285 19759058
728 37914093
93 1000000000
864 45711046
271 46654738
135 285829803
619 56916570
843 248842523
122 465527871
565 29119043
450 13494687
726 1000000000
501 20724169
884 463150103
418 1000000000
513 53199561
232 254469947
884 23237196
537 1000000000
261 233637006
4 14330244
59 99125652
177 684445513
384 666844745
696 478689762
251 21855686
265 180735487
484 319685355
316 26520499
163 113887879
265 37034698
145 22841670
656 46035298
596 365237107
769 106412237
533 267256176
444 479718777
316 284937475
482 2664108
626 214044242
97 266989152
405 1000000000
563 158493448
831 8369410
190 195443583
846 89625679
996 55586904
652 14816405
884 314970739
984 91845804
165 270860186
202 10118974
937 42767582
857 99528604
951 182114978
47 887038314
519 89680343
187 108509813
769 264085745
181 11257723
405 124919690
389 109400719
715 90759530
548 10196245
75 212512355
40 81803724
6 479146903
834 47456469
298 13429951
50 803301595
864 77339419
553 164842205
729 256694983
565 884341111
371 1000000000
192 248901780
880 34342901
776 256516988
262 69737099
487 454611623
503 57761052
100 2165708
538 43842225
470 154653846
239 448109623
255 1000000000
101 66901617
350 5356812
310 649999534
395 53018797
265 437389081
398 73372221
158 1506583
327 1000000000
518 60573769
830 181734748
327 1000000000
884 537042169
10 24346454
791 548741204
959 298937211
400 830953394
47 23172031
512 106826957
360 1180844
5 10978424
388 448735589
449 192209389
865 446256200
890 298390261
209 104650230
946 62630614
162 176514545
768 709955901
582 21442525
811 121234030
828 493356815
941 144452290
92 411113043
517 79066062
462 2127819
427 282508701
2 99901014
151 1000000000
920 419643120
361 8864866
848 103921438
401 156124896
322 27284844
432 2915609
366 1000000000
388 236312380
629 1000000000
430 902337833
157 466731855
79 58479007
944 2908959
685 124986164
164 110931514
562 148377704
467 1000000000
396 674662
195 394838139
469 2921521
622 10942221
156 617029159
3 129671061
632 63837689
945 369212426
307 8288598
826 115130497
324 420607549
717 1000000000
155 1000000000
730 23396142
752 1497040
113 66234729
795 390523835
490 52011628
124 270428950
926 65876731
979 56020257
435 107178935
57 9398605
778 62461338
588 223880590
596 555468415
117 311812316
535 481252231
173 302531125
636 111127943
298 1000000000
756 139388063
70 751448296
774 288562713
288 260327850
273 575666163
607 487849414
871 313801930
453 1000000000
367 217809781
177 34682257
25 12866798
883 444670867
437 195830384
19 25336077
891 482775613
217 71826029
163 1961297
749 455537908
405 575228873
727 109180380
761 27100844
311 142465330
839 129549022
454 619156621
328 673256065
930 50772628
618 450399055
420 638986476
142 1000000000
797 1000000000
69 291649813
891 15624633
29 79714801
400 579614316
488 4986761
315 1000000000
341 444924494
467 1000000000
275 176072994
378 666114122
300 111510248
991 34535338
487 102386942
314 214438549
188 77986777
35 19540842
803 285112
530 1000000000
652 30782938
431 125789333
959 155956867
874 80009376
972 842148580
195 233785324
324 20040116
323 354680949
885 69505802
384 154078337
312 299284308
723 43997668
406 113015084
69 71050290
101 1252349
724 104297980
87 190274399
698 883351355
714 180003666
646 1274635
800 280681320
487 115734043
944 25698792
519 276110220
834 164641413
701 163829796
286 194397477
417 177710924
795 181817595
171 1000000000
571 72750580
907 18648651
614 165286124
649 11986534
98 47695116
493 149263098
344 78657082
719 45001035
592 15145211
247 200337231
922 1000000000
294 28706998
999 1189420
682 144430106
805 293134562
293 91258274
14 413281808
517 477442455
616 828117
988 712075
701 1000000000
736 52694841
220 53477019
91 90938998
204 274050122
220 382520181
191 1000000000
291 12136623
444 155850070
944 136806572
571 143029655
595 83320801
252 62185564
948 188258339
967 85729819
811 1496832
284 473256062
608 81489112
459 39257407
403 154458858
869 19456771
684 1000000000
448 217037650
60 1000000000
653 24166117
97 118910311
389 63198662
757 19693249
246 19918106
158 258490953
938 894717578
862 20255472
31 30623870
411 117540877
847 629468950
815 271835565
729 204049973
889 212675763
309 107735544
673 256119382
402 406582751
567 508535589
66 36821156
691 1334448
252 19692582
741 517568150
368 506984875
613 61684198
70 234699608
547 333895721
487 328313645
759 81039757
185 204727000
617 284430352
301 1000000000
938 368862779
596 103543590
216 235217850
956 92123244
253 705657142
287 997931325
287 73355855
579 244530968
608 246228454
898 656996767
206 8021008
106 202076730
987 1000000000
181 653490256
254 932558
482 25135765
655 91708165
305 932765332
598 22617502
794 13039514
354 1000000000
165 1000000000
589 1000000000
970 39732943
231 481888591
625 101556715
158 4746922
482 1000000000
995 5284894
165 668616582
46 20340984
131 1000000000
232 55146172
466 182822823
519 709322651
3 171858364
84 133697050
383 47912395
640 695814395
204 27974407
306 1000000000
668 22008559
433 40041202
478 961196613
127 74838028
690 485188244
971 146338591
303 323321274
485 7748491
127 472656274
764 41459126
593 38177319
530 186134051
365 393603326
110 228435274
859 241060145
656 210784741
75 12005584
361 1000000000
157 3820757
455 234185624
570 1000000000
179 30604101
984 254713704
229 209952584
472 116492310
46 179151994
267 362951719
676 15599449
887 92821814
41 685481856
518 13156376
435 130917957
607 39055184
588 1000000000
873 6102754
299 389476330
902 1000000000
816 168926754
837 169404160
802 356784444
382 1000000000
107 66997732
593 575001711
74 664081602
982 1000000000
479 225952279
453 130031309
866 318139
510 138056840
292 32186685
625 129476748
819 708205290
798 173257233
472 1000000000
301 172020148
787 236526672
319 78965828
621 51631367
954 1000000000
820 34062105
216 1000000000
698 20661211
71 22144831
725 56443181
729 138191733
503 144858014
461 76435744
143 40915762
554 415747859
501 129764629
194 1000000000
256 1000000000
884 51726880
106 25963859
144 21439775
618 581326432
606 386700342
480 343653367
782 95366950
444 333515412
496 343967372
662 416990739
436 525417292
735 49728183
955 139883521
269 498457718
971 18296424
81 859530786
477 5750934
692 548988084
306 62372920
684 155432494
672 20474055
251 1912129
761 10396364
199 592830300
579 179486268
674 209477630
176 142860906
587 132705994
855 84549575
289 112351505
872 1000000000
654 143435142
626 119308007
761 26696266
167 118486696
450 1000000000
14 26774095
753 23541892
815 1000000000
38 64378733
331 160784686
281 34213744
720 953495629
339 758996888
231 703523551
906 69946073
760 29089153
927 151252959
732 235462692
659 15292622
313 42497376
412 203534705
841 824279533
44 229316814
986 32754
185 1833760
926 141878649
101 6939781
371 33421034
943 321646789
755 37835336
198 97332663
45 9609279
652 405869794
793 411676319
72 530900596
151 8411306
978 201145695
967 6566842
602 430262686
585 1000000000
208 223315834
357 367434883
860 761303215
699 54968415
383 12784002
803 889794084
599 165985882
542 169832736
613 17404428
914 355383566
386 321291748
649 120292227
548 79654664
65 85542744
77 298380353
636 3289713
251 247900270
848 94795510
120 44459322
927 1000000000
170 162192744
136 43461177
435 126790877
114 291384208
482 69393612
263 391810335
663 13128813
190 51812440
410 55964110
439 230188130
411 1000000000
682 383493382
954 167452511
7 783872131
479 85749213
935 192184826
634 439775496
128 1000000000
460 2312174
3 768130012
99 175673970
752 397464599
864 380694197
352 94172015
596 1000000000
233 327613805
485 99644884
957 8795920
749 182573846
595 14105584
563 194969277
66 32096470
574 91135263
412 310935685
872 124123008
400 4023389
784 536648846
918 192786415
54 91805283
334 208342421
226 78926724
1000 8318526
132 319131768
828 12317233
44 275142131
914 1000000000
418 163218742
426 56819500
214 61882531
700 152432481
697 114314085
697 457010199
793 61683163
487 89505197
615 32521694
151 1000000000
484 134420482
690 240167403
910 351721534
766 263503896
407 193893902
21 100834644
318 291339401
630 359014447
562 46556500
728 648556123
677 1000000000
741 1000000000
582 89010924
708 16980877
853 446835149
181 495379364
738 127225068
704 346303937
77 33205673
461 118410034
478 99767734
964 145043888
85 132876995
797 158245603
266 5179060
105 284724037
894 16403302
414 110563075
903 493918848
957 12427210
454 42091586
135 238075141
460 25615679
578 181686404
471 36986383
808 2356250
825 48405215
583 57568326
81 1000000000
281 130754057
422 5701041
93 1000000000
682 65604262
323 168242687
996 607762235
419 53014951
404 328556841
212 195420420
450 816960988
496 665436830
366 145540748
799 116248826
112 1000000000
271 256792220
728 62268942
409 113848924
870 1000000000
301 166850050
794 190783890
731 14904250
581 1000000000
716 236807621
77 2621001
142 89638003
868 601018766
643 48240249
832 40952571
57 79337488
963 963963838
82 75099937
659 192721828
125 281564556
882 120076353
865 7984152
671 14315488
728 225053793
898 218477707
793 58691963
763 915291323
148 396851848
922 1000000000
65 776314178
463 110435551
296 166164763
274 1000000000
153 297081813
755 1698734
660 204740154
818 1000000000
793 192540657
191 1000000000
793 15800587
467 45758152
586 112098951
980 1000000000
574 269638879
596 318020507
763 1000000000
449 232477634
731 66270883
645 167239917
700 320177061
358 576871644
616 132519331
870 144711010
214 926931996
124 24793883
317 151995114
72 1000000000
759 93797076
50 35904693
115 158094672
418 86413758
273 1000000000
792 39213569
601 1000000000
204 4653338
467 61800950
758 98178606
784 138121835
454 98333563
366 180944706
84 206895480
398 104816010
297 582146316
633 276598060
123 177981702
237 582519
371 216099339
715 209998049
98 108487323
652 173513787
703 1000000000
639 236134782
625 57153217
267 378904866
194 138946492
594 286105920
745 1001369
603 9839271
286 212801418
62 1000000000
912 403503
747 390503059
833 3411652
778 211759903
944 330647
147 864216783
942 15179412
230 37013603
145 553612072
299 114810101
874 7493625
202 1000000000
689 28282206
932 387542902
823 38352000
679 203534036
858 240693511
708 518387948
387 1000000000
740 175115893
99 407822337
621 325301556
193 5634542
737 144923023
684 19691785
111 77634081
174 91911596
759 277690933
614 9629653
192 64310367
427 518621259
20 298497703
991 992429479
738 696668052
177 225353674
522 114433052
985 262286606
756 49505886
367 240159181
192 153661114
492 73782700
694 1000000000
502 2342377
759 182049661
110 538640263
257 4172744
228 258011800
653 15610268
217 15534054
460 297732618
147 125130761
524 1000000000
132 78277767
535 95207450
322 195166224
779 59286742
503 101962644
738 129278520
314 202678545
227 39777836
851 197500973
526 217740241
169 132526033
283 48113450
246 246566790
490 78642687
521 217169685
259 10641367
330 75903327
974 77016792
257 129209047
27 529837191
583 324850479
98 425761888
666 176991742
451 202527513
739 1000000000
390 23170192
530 90951197
52 305441865
496 165092478
99 602443645
731 125373763
5 158954967
309 1000000000
368 212342322
892 211914162
798 213293357
346 268865389
862 347907045
534 186502357
951 4467186
55 329175598
931 194093649
431 164823808
497 173572216
173 301830187
241 267742151
57 104830630
907 315507936
523 1000000000
543 23656107
259 280839504
917 25543564
57 308249109
773 55924
766 28620713
712 143633202
744 292516454
636 25785443
576 264418692
578 10787188
311 394382409
547 1000000000
435 225848780
925 471466743
838 261365555
66 459585103
174 73739219
240 605237300
165 76399415
985 71610
914 224557124
172 236737188
476 3862861
409 384347528
949 1000000000
783 253823046
36 399203
24 93851189
385 7522762
171 47349730
676 148999807
688 568505540
85 717708592
336 250792509
884 378304964
17 120401009
538 155698215
12 275408905
669 303830885
521 240485
638 84828827
801 127894505
110 61411896
978 135420777
995 1000000000
446 512658659
919 278048054
571 151225275
736 30900592
659 235162951
928 126568114
380 4816237
110 140017035
96 670995649
361 541130030
926 71462715
803 34076956
350 239642320
587 76907836
568 1000000000
385 34945892
988 126559184
221 1000000000
98 74673761
239 95307460
626 556115667
63 1000000000
668 358717804
21 263314562
1000 22838953
10 1000000000
775 6600682
132 714786862
335 1000000000
173 505277072
65 8468970
795 167638050
366 276187
919 1000000000
565 70060
226 95549675
933 1000000000
43 41936946
832 94605560
961 222274563
925 24077622
118 119960281
75 162476363
289 16242817
844 282175507
674 100571697
47 75184839
1 10696460
444 508099617
318 296434121
243 1000000000
969 566121159
140 760659505
858 1000000000
296 412072978
593 480747324
245 667269328
503 286996503
348 323014748
930 138885225
621 58731111
939 229157419
257 126151293
627 700491843
934 13653037
976 366380746
174 16736065
52 65469258
128 20876245
702 316985674
739 729337323
725 1000000000
129 412535146
531 303817053
81 55382215
279 346158052
467 8936991
729 30014794
287 1000000000
49 1000000000
917 281283067
703 355147248
861 296229642
491 500359777
311 46484780
477 46429602
147 78469301
333 894203895
417 6372853
68 220025083
450 271176747
48 1000000000
428 60162105
850 113176036
856 101610339
27 160306
983 162352026
585 334746514
839 727102506
734 112609638
954 455779549
409 488870359
31 27973764
361 33144482
69 80967554
624 47664228
814 102182176
77 514365760
465 1000000000
16 415975501
622 41722996
937 12650772
509 1000000000
104 190253610
310 352524039
237 57302490
729 795696666
976 1000000000
846 8744757
569 293564857
942 4985691
433 177439686
935 217098494
966 26757979
362 66391996
25 152211934
744 368164869
187 1000000000
127 55934731
10 416095252
121 406838944
808 146261474
588 4632343
755 1000000000
914 365656428
365 122248572
586 69498378
261 68899262
868 326969035
939 130515364
111 71747952
399 40610842
685 35924074
441 143010624
45 383362244
105 80034378
991 181261453
55 133633476
812 29614016
859 106384399
882 405449281
109 59841656
162 29407139
621 82366984
4 235212491
484 41246571
129 1000000000
480 124732954
431 200429290
531 124842450
408 122482414
923 47650952
306 71793918
42 171083383
487 36709529
590 181223208
149 702349259
289 295587666
286 190823079
522 237938815
577 184039253
497 25282012
38 65204336
422 32465497
717 258900270
601 260909694
574 52892317
218 112668265
9 1000000000
529 1000000000
438 24470486
142 176796374
189 484005650
897 56265597
822 321784763
986 623050
114 322915842
698 582951903
511 34174015
159 187641574
815 188207123
59 513682925
784 12253169
60 668349522
516 255838358
940 1000000000
489 119660770
953 213222717
425 256196874
421 180131626
835 835887102
167 20226919
614 1000000000
671 41924711
564 57723217
117 7349981
340 125175772
952 51578748
342 221695701
371 157688237
362 375796692
443 1000000000
592 288487375
385 22433305
609 102660745
581 628688209
27 291158133
855 83855984
487 40333518
888 380883529
302 306222844
678 4292080
198 1000000000
826 70410170
592 1000000000
357 1263508
189 273127589
790 80224823
492 14053310
916 10146151
748 912356742
945 122138591
911 441221508
684 394509840
140 55881679
5 294126568
643 209731887
315 691190242
164 46362669
864 1000000000
871 418933772
291 337753036
148 492148470
413 85785399
99 3532841
452 1000000000
596 55009193
265 368801005
79 151102627
644 234776771
885 1364134
533 1244818
748 24777130
245 125324050
237 220968842
498 259004557
769 107210626
206 589950697
398 126515297
575 141098063
702 9320685
215 1000000000
16 37614634
533 424065069
627 212427687
201 338652813
337 71808232
802 26945988
657 986801684
402 125997273
355 1000000000
776 154804697
735 26093039
308 51196927
461 287656436
958 1000000000
837 32259748
631 46960210
855 80691927
733 116189343
660 108950461
409 32609607
554 185538111
843 158576332
746 172866175
332 169556050
741 9798763
210 90756593
809 151989412
543 57129445
936 3673002
17 32869435
472 2612329
818 1000000000
507 3016250
529 1000000000
16 122629222
726 145756038
159 296332536
776 578682
760 208225093
785 1868999
538 20103096
112 1027776
679 519561326
941 1456958
215 523715614
272 14654660
256 84994596
450 13891492
355 31683202
49 105384922
800 1530989
14 165484447
671 235296621
225 339279060
113 1000000000
771 1000000000
100 46276759
666 60242952
642 665624
184 960609481
817 220635342
99 111960381
851 402886949
13 324783402
583 46695439
685 133758357
12 1000000000
906 59406678
332 25895538
414 3701106
46 540667970
376 319315251
194 88189562
8 30002753
248 333974991
294 4755067
576 28447351
506 53130183
546 10572761
836 1207832
110 401409155
413 26928643
957 9717804
307 99648333
813 446379271
295 121628345
711 987369308
642 729062138
444 378554733
978 576332496
778 18005881
369 904617
91 154954282
693 53088985
141 317680
680 43410302
618 1000000000
97 24508840
449 41033112
959 51360343
674 6139403
164 214697687
28 76348725
431 515114972
401 515075586
808 11226190
768 17414759
983 332999479
1 128537644
452 113662597
228 1000000000
103 20718409
554 1425229
1 71131769
849 65618877
440 482196909
234 356521634
125 82957201
142 133338292
353 5813446
267 95399879
722 20232160
483 140754613
754 16097857
772 450706700
911 134344176
856 1000000000
27 717555997
109 1000000000
52 145670719
821 219753633
36 170147524
471 940041768
842 12826441
467 1000000000
774 336992261
697 323798765
96 123866901
241 1000000000
192 1000000000
995 9995408
998 1000000000
399 1000000000
618 31168325
5 400505616
492 181508591
53 191836280
69 82842105
240 1000000000
163 48309677
92 209898736
423 777754531
74 85712430
210 18336495
555 3659043
434 104574658
5 13948786
769 4698176
546 27958099
398 68457879
985 270065311
264 736415268
490 151872033
769 673523439
860 77822449
984 114018894
513 35687626
565 343751724
472 46694064
976 1000000000
185 123461689
921 245021379
380 1000000000
288 154814483
585 332583603
93 50593663
57 104965748
864 227623718
210 191590732
426 118420005
765 55525568
617 9018948
938 145824844
22 89538012
922 328626048
322 217353935
491 1119153
11 760440556
895 180748543
579 493886490
949 68363924
201 42737138
780 78347418
868 546654678
422 318446596
702 110620895
898 48611765
70 11750056
976 183475311
892 218204663
280 27746598
104 506994005
186 957272015
954 13234809
342 208750696
826 607638474
532 1000000000
872 234824797
348 309640411
460 79001508
598 465045840
735 2746955
258 1000000000
839 681893776
849 541315944
269 668264425
817 287873854
906 200870799
796 127929758
252 384132227
800 1000000000
13 253459770
943 988929656
28 96893468
232 94448726
752 18862060
810 165449103
723 136904993
71 201511934
988 440557581
238 253143293
187 306851169
943 56723044
736 1000000000
26 12929617
203 345303844
199 163607467
148 64959440
158 70619530
475 73809083
239 16733669
960 255395826
443 513420309
587 31754060
120 117171142
397 1000000000
511 1000000000
604 190387091
681 1000000000
2 618282192
828 985724226
653 178442122
426 118635946
87 152330649
697 3423366
518 10980815
915 36610757
924 233701909
23 404803692
8 135089100
645 443046304
738 304767
716 191875374
42 20834565
774 155563206
504 193059496
490 231233875
620 54049843
792 442455207
838 18539991
161 15046762
422 337732448
243 265478101
12 216554744
487 97058386
640 1000000000
725 5990175
619 256556521
350 54880503
395 24092994
272 24531032
674 11758653
317 364582404
758 100100958
707 31812503
641 223768910
372 52957970
361 839375775
342 737645379
504 46075169
499 128387436
301 200800152
634 1000000000
296 98316133
939 65835896
857 1883710
998 1000000000
616 1000000000
891 1000000000
253 387940198
994 449125005
968 410880906
859 563997587
945 223711318
334 226512882
944 224954175
939 83860002
453 277594641
435 29901961
817 1000000000
804 51169495
562 85577942
752 318369417
58 131324251
285 137693197
871 11492499
197 357230121
867 321260061
774 201137001
324 290744400
866 665059024
996 1787814
384 1317306
98 67520331
255 297850146
590 100711145
537 114189529
119 65715755
781 38858838
95 160276910
355 571910985
37 201322035
259 78820716
922 99855904
381 334361353
164 193824582
178 428390485
124 112966502
360 35090796
514 320928468
336 153134198
471 532625591
290 8979410
305 787668757
999 899715527
761 247101537
541 456598160
456 467612819
110 148432863
141 607796258
521 76614619
55 37064288
805 53458983
360 13664455
284 287619871
263 85595606
869 37143119
580 1000000000
496 789828292
198 42235454
61 179383803
615 1000000000
628 926484037
166 170363230
621 989178939
643 197179376
992 1000000000
63 54733028
261 117770154
960 1000000000
340 1000000000
71 1681711
206 463221439
116 680295566
377 12148994
208 15565231
758 106011406
649 168134357
742 119309202
905 111930723
23 274183074
654 429958038
131 165544481
34 244846789
41 141810678
572 281973049
776 124034843
876 289296449
370 262078757
1 183873392
118 12745779
117 989631578
444 333563099
423 1000000000
220 1000000000
767 39246047
550 113537220
173 235594274
146 187171098
674 170491025
616 59478215
36 1000000000
897 75634722
236 92325148
923 3077079
66 689864608
887 16960134
487 306962143
542 1000000000
489 6287930
670 65884881
778 459045803
905 669490680
424 103141357
381 28634970
365 165159488
660 13425830
832 481138851
709 142928496
377 97096432
24 255331028
767 1000000000
589 389383812
868 297022
763 639375657
887 32551583
724 155585879
264 161747
352 409608750
719 301600083
829 193921657
916 199630745
412 216713897
224 24312091
861 1000000000
801 135491380
136 1000000000
912 460376713
366 83325733
46 387776348
765 32833879
457 55959466
591 31231606
219 9921196
210 81575485
818 818519592
768 117691293
704 67183695
256 566029661
20 151810111
729 656790124
77 430509713
245 63186511
669 792895838
979 133130712
619 113986525
803 16540115
263 25161465
221 1000000000
65 702934653
953 143917145
137 421514651
959 132803863
95 269524425
639 11116634
732 47828933
233 180734563
398 269201521
46 63944144
982 104472463
132 199058638
61 1000000000
533 10963366
953 89504700
455 241385232
900 161449174
52 11895829
68 252497296
650 676119434
187 1000000000
715 67041472
616 45117509
910 463723569
762 48091190
866 1288780
499 7964277
361 121223288
26 35053403
210 60927144
671 238863093
149 78365695
946 847236498
82 143764044
411 244120508
33 168383537
26 891307375
947 367042280
816 376237587
574 280940440
723 287723508
843 405694813
356 291803059
779 7813438
356 78023748
876 1388704
633 200147081
607 152770837
69 366037206
317 101136869
94 849537608
573 59211950
558 688944277
302 115254425
739 6556341
682 989317390
815 420052168
672 1000000000
833 18256645
200 336143618
513 634933047
650 1000000000
351 241568994
830 196095015
787 51241941
612 52661747
685 22801899
940 34293871
373 164678352
822 356979207
819 39398179
802 144525886
280 14677781
569 308303992
458 118857010
177 112322551
682 692333952
403 51248418
729 246423143
360 176148647
461 1000000000
502 107718972
264 28863920
663 38735507
33 55985353
378 1000000000
199 293381113
719 139674277
364 103191207
405 150643337
783 458701855
318 14300262
904 42677988
849 40380984
855 981310
694 130958954
492 8366781
461 1000000000
399 579516250
430 14000480
664 86709939
625 275805331
335 152262983
623 19089324
285 1000000000
318 419045110
376 1669732
423 1000000000
617 118303724
819 580687888
929 248620522
416 87151798
14 1000000000
736 89043350
730 29806688
625 25487543
996 4226248
605 293985456
83 67239460
99 241889525
601 577123743
771 1000000000
413 19179733
477 582517479
223 77645294
81 217214919
479 20665115
143 10361155
853 325617442
663 695133493
265 140937911
777 18772429
355 332329927
405 46405010
427 64297933
835 21737652
442 13617309
347 70263042
174 614933727
406 1000000000
24 114821545
42 127619352
265 182100955
233 44992376
367 406686036
49 581340187
268 128272305
492 1000000000
158 31988540
521 37898015
359 36455600
415 253637311
534 351757037
992 144535017
795 131680426
187 624343653
6 24203026
592 28099877
815 12476990
719 134145402
942 292697748
240 232234085
939 197356322
915 24661813
214 1000000000
904 122446689
439 62070112
128 70143673
438 318314293
865 60749772
404 92136942
484 560888378
695 114441689
250 85706138
313 298840228
225 95225724
288 82726137
147 131504673
654 771197332
334 553010249
905 59520062
396 427999359
387 62328425
796 178880217
435 1000000000
806 246403001
545 586748307
601 201001658
853 180061134
583 314189932
535 288978732
167 74397206
15 493710036
113 946061471
285 476529376
958 349875661
889 76829504
524 336598655
443 198086795
852 573504076
139 439433175
518 140983596
746 184679249
19 103143202
38 76981717
937 3464207
297 34482744
274 470017852
889 161805982
436 32329633
240 682821190
641 403609909
300 23606286
575 254982527
463 544177035
192 501142204
32 361384660
499 217454407
711 110392535
704 7602286
140 1000000000
647 1000000000
583 227328252
656 21266954
144 965111593
851 578681350
415 642912692
432 206939472
572 123996121
631 20393345
839 51846708
1000 85758883
664 1000000000
620 228191108
928 50293301
249 43784194
557 178305169
904 143015087
848 1000000000
266 800343847
298 109566353
782 34881577
586 420406565
883 782806857
735 51914351
259 406058138
563 67788482
197 106461246
37 311262972
464 440591556
5 1000000000
142 339752772
986 241174645
102 165439260
902 148714969
944 85260678
8 57002417
60 432530720
449 9047002
354 315866230
847 1542723
571 796929633
971 257492429
933 7229065
29 236647661
89 18556733
582 245428085
463 396621039
148 615966610
936 131310476
928 70980043
410 532156547
843 648424336
791 153456048
748 239975676
982 55617768
618 1000000000
134 119966411
551 472208398
449 1000000000
298 52065523
22 621058555
978 127629590
645 16907288
793 10397810
150 85214194
606 2777137
241 328226058
985 31524471
126 281842849
194 65290911
693 1000000000
218 442032684
374 1571076
871 151890889
65 1000000000
890 387940263
975 157279624
347 955137897
718 393967412
59 93354222
599 53146648
752 107769844
819 89657909
876 106281708
472 1000000000
357 33437427
40 2998467
757 11709004
658 773142975
451 132767472
637 9865944
311 1000000000
803 224678196
896 14154467
43 175952612
48 1000000000
821 2441001
166 126048742
937 1000000000
594 157965959
583 390614668
692 58876620
919 196413223
509 1000000000
89 405552018
555 199107031
86 23445340
151 1000000000
852 285932350
953 568928587
532 306568888
170 4204344
439 476828231
432 340942068
899 274872669
805 611637813
402 1000000000
111 106402616
922 1000000000
232 238565598
373 447342070
223 580342107
658 1000000000
99 1000000000
849 142530268
990 111870512
626 277672473
55 46720233
436 840161309
486 132196091
137 1000000000
67 55774930
856 377548455
358 1000000000
970 28817740
351 469678410
173 22527290
695 164174787
402 66211235
924 96669106
361 757912883
127 94381352
571 5029123
393 375420055
894 150975447
352 36601482
844 47372768
110 167945855
275 167172651
529 305633253
149 185118501
731 302778858
312 1000000000
659 32647784
598 672594487
104 336139732
118 27346144
12 29315945
48 1250892
198 1000000000
260 529662039
830 349496769
706 1000000000
60 45910145
802 4516030
808 644786803
876 13585470
2 45167876
304 1344020
603 19328749
470 108563255
777 62303611
839 822676027
805 19877317
113 970040635
240 365442803
54 75606801
208 209371635
828 167013995
767 203520630
725 7272998
779 70148250
103 1000000000
662 173006000
972 64716512
423 95497969
707 63723828
293 237604665
275 215590134
498 69591822
174 1000000000
709 1000000000
531 349246012
750 268392
34 70263792
245 52613093
219 506882188
258 139487087
366 151386811
765 91900250
36 211803481
294 24205195
979 787486654
734 1000000000
588 7629596
659 64668731
984 55890784
446 247220388
869 152593563
728 97877709
4 249914894
127 44513769
334 132540820
885 76402736
66 230618817
369 659998699
455 201488615
690 104530359
351 153620392
634 333709743
721 532339208
832 77132060
381 450197033
356 126274144
395 904715590
382 61655385
507 250685690
718 48893667
797 650698548
324 1000000000
345 2113391
776 73741170
71 36081068
442 40161320
167 27051960
531 44921175
850 175045624
913 21217149
782 510595816
261 1000000000
300 643731154
744 681764369
845 613398920
496 84946486
599 53044032
159 267643458
796 11228236
4 302286812
611 568473186
350 1000000000
835 522452356
519 161654207
502 68622385
94 442698341
467 1000000000
83 12395904
458 154193408
54 112687918
67 1000000000
423 1000000000
182 960160333
270 113637912
235 147160494
419 767612245
346 38161096
934 347900314
300 1000000000
824 36918993
695 95193399
719 109821869
100 290039442
548 142083588
908 174031831
536 16967498
821 195757161
337 50260251
73 169062288
513 12387420
966 747103072
111 229169876
230 1000000000
74 317066684
536 24647544
540 209709621
780 288450900
188 1000000000
162 23135583
186 813634526
82 1000000000
518 440633510
731 409413493
952 474473868
792 1000000000
928 159160307
606 28436003
566 1000000000
30 17794865
538 117392216
832 396631672
284 265870564
4 34815168
285 129676599
875 152568949
395 430271852
883 466840191
432 1000000000
566 205839213
554 132544137
874 46324449
67 135017121
561 301265439
57 186573746
42 143790109
974 147448707
444 38737560
761 9133237
569 15090211
194 84490659
272 143424570
761 41898284
545 148215384
806 277341722
476 75178985
665 1000000000
945 766220035
586 33278710
40 73928374
665 26135232
913 113209955
990 12794569
525 140631046
257 43958213
666 176161823
827 14966175
153 108689692
514 78073265
251 28073752
840 363314051
726 55165893
747 146410000
596 76044103
493 101582535
995 92823384
156 93838287
309 536796361
498 45765847
425 60526879
542 39060443
959 120362461
256 27094874
758 259040147
784 1000000000
960 1000000000
654 7608215
980 21730490
562 716942829
762 67832271
700 34079469
635 1000000000
396 1000000000
93 242345391
490 263210093
105 3782650
478 42764374
119 69632810
825 536414453
528 325430365
953 88136130
66 130795027
472 786241743
175 27819188
444 32223365
653 898620279
159 59615978
110 83070229
167 20094375
440 485373439
374 99214859
237 78220611
963 1000000000
748 405005159
934 466171946
421 1000000000
559 60142889
216 28141415
773 2037020
301 41230143
475 504407308
548 1000000000
246 59364398
509 9328393
759 396202548
920 306917640
542 614255151
405 1000000000
979 1000000000
565 54378809
47 48295914
830 84668048
384 189731166
457 152924739
167 1000000000
911 509287
381 357631746
927 328493400
161 95061545
688 135943810
282 281601394
548 5542981
138 704466767
298 44070694
64 66650751
761 80828959
772 273581288
635 913255771
429 83372602
751 289214428
341 181810002
429 1000000000
331 2694075
101 21908495
512 166129117
695 17413019
850 382875482
660 97042658
34 43177182
594 1000000000
344 114614077
18 55083014
148 351487678
788 172617045
847 520305429
737 416559270
415 128259238
15 265523079
806 35198355
464 3575372
130 129370268
203 42771003
325 9162910
815 46678596
582 276885252
390 1000000000
397 43608494
559 295361891
841 1000000000
362 740939446
708 60631826
191 136245498
213 782963870
550 22718229
804 138008216
263 1000000000
913 78337379
746 40614346
341 1000000000
327 839022604
542 483362553
702 68423399
837 278087980
471 53748307
762 17039084
643 212356353
166 465585492
784 1000000000
847 432504900
176 163822803
263 536557633
617 1000000000
52 126420815
661 531758400
472 444889731
891 146408718
290 249203398
730 164869758
506 43388596
716 173912472
127 1000000000
832 723547226
315 4521054
238 321985067
101 266015350
582 0
621 51749564
816 9547127
755 602028504
516 77202047
927 63843604
810 1000000000
82 729212382
315 123504406
562 219556450
181 21952537
240 740006855
1 14500197
173 251906239
824 9696562
711 100552366
248 196531382
72 82635313
115 6607837
694 12640954
55 174704301
875 1000000000
806 235716081
206 327766588
447 339570523
222 1000000000
106 1000000000
301 325848909
774 36394118
810 246282227
469 78796336
437 16918573
934 857211450
382 306794602
841 323008932
421 86172237
967 10401053
434 97378425
798 507186866
910 21804187
375 3879548
623 95563884
162 13133484
630 306150150
112 105971290
996 1000000000
63 82396440
991 224469578
153 9411851
201 239899845
4 350421407
880 528294140
866 286254808
38 1000000000
65 47862973
322 264235817
939 3727942
435 172794805
647 27865439
211 57747
781 3762699
57 220683632
541 70769982
733 209929767
391 33435507
351 1000000000
163 350610168
663 243186341
833 274903956
917 81439515
417 1000000000
234 1000000000
363 96861775
44 1856281
984 538768833
820 224229295
710 19026165
507 511204505
87 294984
903 290717641
305 589260293
954 266621400
878 32019018
874 1177691
364 158585221
649 128955673
589 9597897
37 88059101
968 34216159
616 1000000000
84 56719613
505 504764067
355 129047470
728 534080777
236 127783188
165 27121855
695 96466406
304 20957038
116 264884849
905 1000000000
355 63633918
208 15157569
933 13186252
973 8544968
144 214511621
785 113559543
141 118031976
506 174053000
845 134281059
201 129932268
134 1000000000
223 156461996
305 83581534
482 72348543
207 611408191
884 271708250
591 6738528
292 2033931
792 342012643
665 40903660
700 336974246
589 3044510
690 255112679
151 158181585
730 209118532
7 216525557
68 80556495
965 352738565
88 194146060
969 766070273
678 616769871
163 310987437
70 491433111
3 159325494
64 243532615
617 66029129
844 1000000000
542 1000000000
683 454857363
416 103051900
11 281048564
664 1000000000
853 45834525
111 668727810
170 15822535
179 249044573
712 122717278
502 272094666
529 114485618
591 59910311
860 1000000000
165 8908844
912 1000000000
450 61851480
615 128078150
269 282225816
888 40381001
742 23348581
915 1000000000
437 344174735
392 1000000000
138 260123123
207 1000000000
229 64946234
176 284191
574 1000000000
531 9714544
29 261613014
937 54120260
43 64465276
768 181922228
30 18756825
105 14028284
287 107246628
853 378189966
759 598469
466 294146693
948 1660106
122 72120946
88 102890159
635 269127689
146 189735896
711 1000000000
841 141498887
733 1000000000
991 11436640
565 454012763
459 32950838
999 70754067
53 9175535
634 319759949
525 332679029
824 132791575
995 321013295
113 85808350
543 1000000000
155 29626361
761 85168146
311 303495308
433 203360975
13 802961457
135 209919544
125 2276909
908 290902866
624 1000000000
326 88663753
876 55289267
919 35866736
131 42704945
141 186233956
363 134007257
874 78223020
270 368808696
148 199607910
619 82757643
101 68678065
617 381738199
92 150680685
778 108909710
713 159408278
477 317126015
100 981753303
290 159958520
277 19315777
993 1000000000
236 309967294
506 1000000000
497 1000000000
797 116615165
348 59915514
394 5381173
85 218235510
289 93197920
820 7393986
995 14426553
914 107588718
742 169484420
605 216825909
668 15072853
167 20963033
755 63983926
230 139069273
933 7265320
708 219879740
288 330383849
391 327466
638 76646506
233 19817557
750 110111425
161 83340476
871 135293843
351 406544995
67 65647610
899 75764281
801 137048479
637 611963336
145 169991423
589 1000000000
667 1000000000
963 998066617
655 33289664
239 14355940
814 46654361
441 42999136
990 76686420
593 266346189
680 6781578
144 112364015
421 320790397
148 1858250
347 133177280
614 27817166
652 90382554
559 143348712
846 1000000000
742 1000000000
995 138098254
890 122813910
257 289835064
965 1000000000
354 12807553
350 111093867
133 44544088
341 1000000000
802 407729528
697 6253822
449 4648214
36 255354049
58 152054916
789 828508086
861 140988096
213 272134726
554 1000000000
706 160003009
737 1000000000
661 178146974
610 297732885
614 7229389
598 1000000000
446 4844665
75 137704406
603 120696507
490 50745640
806 293012974
412 538910523
472 95427353
935 372553762
72 121083416
269 1000000000
837 1000000000
493 119806476
289 366966540
535 134507866
395 443747634
386 114926673
163 396790303
744 98817482
712 266178399
456 264998970
668 554046986
770 219243548
46 183675215
694 788607489
790 315318213
324 98279432
957 75532350
900 537762975
89 4222463
391 1355502
99 143324695
59 118484470
843 152991657
481 65269658
690 154010746
490 37649326
894 19397416
684 28989993
417 301169245
713 19043446
353 1000000000
696 589899521
216 286682461
624 92507091
589 173390599
419 125098777
16 8947806
336 16809869
272 432218112
735 96304534
823 394563045
896 194239308
492 178364076
107 1000000000
959 176156387
96 70064291
424 686624
967 96386129
592 1000000000
896 295424989
221 46974760
59 60655068
800 547171
928 214089856
921 371299509
504 352344864
537 100839249
145 33033395
950 19891784
477 542463748
522 36541711
978 39079369
163 1000000000
482 35321466
851 26858431
276 375644776
169 1000000000
751 1000000000
180 227516408
781 215611279
638 939720748
901 181419634
574 129668835
367 528569435
876 1000000000
587 101103365
64 870330730
561 1000000000
498 1000000000
105 684183404
50 990848841
99 120042271
449 383495905
928 84343426
997 193113995
174 142579771
647 191068295
166 190965543
472 96605189
377 640387745
470 182892307
901 1000000000
947 110020509
788 846371236
677 344314768
212 468182058
590 71977674
615 379070182
21 2058804
948 165033257
809 16177414
779 52299863
700 204410729
619 198879625
845 76665263
350 258789768
492 55740721
259 109894565
705 153316729
930 1195938
52 885832648
332 3201370
389 929687390
407 285222837
365 41681235
204 554215454
690 829990594
235 161942194
173 1000000000
445 57606906
967 612435536
248 83594379
702 152820560
790 80002817
380 187038410
53 27914689
407 192677054
879 580379641
209 126441256
74 1000000000
513 134278403
984 199829537
78 7837646
40 481230489
186 26506290
714 555766163
740 66542214
582 347901995
164 157671832
676 336393254
330 150719858
868 118364257
702 352862837
910 641924842
832 250627149
930 342347743
65 96608647
72 150566109
319 147828910
201 206512160
867 71342585
427 512189316
734 308895262
503 127914691
814 80599407
446 899580112
341 54804270
839 71897733
873 92966887
305 602408385
980 11749969
54 197815383
396 562430258
37 89328165
603 20479593
373 5897218
320 347810962
16 282056565
227 1000000000
77 196995071
532 1000000000
772 321986074
75 1000000000
677 9487597
752 70143766
536 183373461
187 326979869
654 71726845
268 8389594
101 239098874
348 1502069
78 1791226
593 1000000000
665 170517116
780 358882817
711 72728587
646 250251599
958 1000000000
493 17259576
968 78773469
3 395216749
308 657944975
951 207195113
449 306875184
632 12309082
25 394714787
552 17016477
555 411520925
294 164337853
135 146818179
26 1000000000
333 1000000000
172 47895287
53 52413307
388 575657022
287 2113867
130 139189024
283 1000000000
38 284291368
209 158474011
864 301056288
729 45226374
313 161024735
436 181104244
735 76124672
904 116698855
283 5680579
214 23334451
678 81449557
647 498602916
782 199670342
817 239357022
509 220549164
270 257006976
738 136329661
613 353841341
756 214765380
653 161439122
933 22421982
1000 1000000000
676 2428027
125 4265958
361 13671053
620 602611134
124 1000000000
381 44118279
917 59934377
616 726312070
492 210209271
973 375856094
81 1000000000
876 322424913
668 11284786
710 77275587
870 425874907
289 33322673
853 345288537
54 19346477
394 1000000000
118 23329686
822 8720594
719 443481396
463 388949083
995 268458270
95 172952254
480 37163680
124 838605
560 34625455
120 546530
394 43779758
450 521548712
190 120131750
82 36434109
532 76741434
336 288759988
339 1687011
148 40811936
885 471715101
270 88640808
385 50663466
790 409597442
304 191254116
948 157260403
208 2303201
720 237391689
714 1000000000
498 24231213
54 36077104
195 99707689
317 254092391
553 1000000000
525 76816912
262 350140230
640 124381248
616 45150292
516 1000000000
289 146525419
859 98104972
271 67666810
764 1013828
700 277645877
70 1000000000
839 8873154
683 119291807
336 996564523
82 204329954
407 48798834
715 69019535
308 1000000000
342 729094774
63 202637987
531 5520823
432 857215786
410 130342626
367 389875029
715 3466953
188 42169297
174 316763394
967 115875548
204 77937400
825 5852867
131 311739306
976 303952051
221 145037295
694 53366552
384 53137296
665 207842106
654 364745453
683 108259823
765 36143509
866 27268981
255 70745132
272 29763971
995 83398621
836 337439942
360 635222925
286 194781364
744 91913330
694 192631871
794 1000000000
276 188078977
382 236453736
128 13812151
740 381785548
226 133737939
372 16959219
922 461834975
903 236372549
808 149478359
795 753833274
748 137022630
897 13959033
175 473921658
778 136834346
543 74293653
620 3500750
309 479124157
696 68318715
874 285139821
271 153406442
853 21392209
56 614650172
141 379031374
970 36174189
268 148231561
951 731274190
97 21380838
774 298557161
972 183479352
319 81003844
964 47780920
522 100051997
515 3584626
743 69069213
536 125308870
750 210689219
596 25409171
455 77987816
221 199912
250 885764464
540 68774610
519 22080033
209 22721169
863 153184575
477 51932396
656 30820635
278 489160305
907 45239848
109 9758413
609 130498403
115 73321973
376 1000000000
166 218884329
514 84268215
232 384275911
70 502802558
344 251157657
107 365647273
134 2794559
971 494531229
561 411674724
533 1000000000
3 176767867
921 644201844
99 341487445
823 26149717
889 35329374
399 232400267
829 1000000000
921 524466467
576 114324875
709 105502556
592 190145993
324 48720553
374 253006094
572 3403631
890 333768106
422 683906785
237 318564813
771 738531440
637 849066862
921 164252212
804 418981400
674 45888800
744 296473996
204 167719021
963 176939588
281 471837520
140 221794930
720 272707580
755 733314001
49 39264887
983 1000000000
68 193838527
778 177554200
161 463502294
283 117313457
904 222616573
666 239534614
377 564017456
695 1000000000
12 708165821
699 149018496
369 590221810
644 274575215
920 321034105
267 380395207
57 949182077
432 156281288
421 57250690
348 759397014
850 10217292
861 674956481
930 172999549
389 806589331
971 81138
114 344251689
295 156695247
710 242938499
325 22309982
1000 12327474
692 40290451
663 1000000000
838 189886804
237 328357558
306 189278542
81 241095927
792 37123781
507 113610453
552 146839777
419 62710995
250 55097236
657 417922093
206 32629080
613 436581941
340 304725154
776 87488173
301 42114110
424 1000000000
583 14882919
158 358702188
203 75720198
59 104395961
970 106039178
37 2034952
474 138639320
646 235879381
941 81553763
876 65472300
145 359879924
33 1000000000
232 103515898
36 263764319
585 30124241
484 227879046
780 67500757
171 28985225
752 469554348
184 24950424
55 40705004
75 161322610
328 121174579
972 783063487
859 51811516
99 62779925
505 102550655
288 49404942
648 333967513
876 189735240
401 419830677
325 1000000000
556 60404074
996 1000000000
490 546924775
266 23765606
1 9974994
765 310579639
667 709429662
95 1000000000
350 533774002
414 1000000000
820 794015471
708 17095496
115 24686302
216 146473124
221 79471524
769 576717297
385 1000000000
201 93546930
247 201157718
927 1000000000
711 10481959
243 17628886
961 83887586
93 617402212
77 116175758
557 485783917
483 10099804
923 115753437
115 213881525
703 181950954
965 457112997
682 1000000000
362 15732884
154 132204411
544 8560032
864 279605350
56 1875816
349 1000000000
147 6779479
343 382898064
808 269782881
424 1000000000
86 26810377
815 237650830
631 73703298
707 6160142
786 93810300
886 8662328
622 226930106
135 663689403
589 186317198
422 126330719
694 9424334
763 16431909
985 132463837
654 872920257
126 311714423
407 174028224
149 1000000000
630 1000000000
367 22880319
371 536581038
922 412844741
919 526795886
447 184219108
304 215566609
854 158672834
247 75928323
688 353643223
365 160981872
683 598177470
24 31388579
345 1000000000
538 232403499
489 347990909
82 2971045
162 42375135
607 91851564
366 4175433
355 157483751
44 4001753
133 266660328
812 228976137
13 256564441
406 249377376
875 114867981
586 26334781
487 12484486
80 107570446
785 860007606
672 47638157
393 703099395
298 36073690
327 41989795
630 900474182
172 69329043
748 135278967
566 273764000
685 1000000000
566 240258976
207 120580621
893 584951791
588 876596835
97 271430869
914 7651923
484 1000000000
867 700104009
893 970690447
814 504698016
187 73701427
674 47912480
384 932103
257 220219303
499 1000000000
738 960043663
52 50918555
661 216724109
27 145965805
66 74162571
512 389106160
505 257783585
299 278171655
874 2832812
460 305960889
581 33030036
971 74573684
915 36290495
264 1000000000
458 162442128
556 305808997
315 233458819
277 577188728
535 98665431
317 50739653
260 34092334
298 141593292
468 997248465
518 578467156
405 401810050
711 54646308
217 132448559
703 132846984
863 223461451
717 225618459
855 310363620
713 368205233
216 210947665
819 63876552
700 223097344
235 433439029
130 751755499
649 157152783
322 321363845
925 939015304
509 1000000000
815 190054730
353 251189108
839 24372390
743 42504158
493 199382828
807 42517513
786 117623606
586 290336607
580 66267570
334 46290380
133 374379689
693 472026
427 83106619
229 261381858
272 430732906
696 693585780
690 94276257
516 253845633
83 63228792
563 22856021
738 25171840
692 86389770
47 643854275
839 1000000000
362 87043745
980 283058537
331 37931172
283 17886313
962 457604439
380 310161753
703 185972873
15 68684087
898 3756417
724 535504502
379 37482355
227 1000000000
250 15549822
5 101383507
432 92940178
472 581708681
355 346608434
814 378633933
501 14104989
261 935603156
108 8651320
711 334225249
98 2413510
2 1000000000
429 4286293
200 198302090
855 217566502
904 461626541
415 64612181
353 1000000000
885 606649133
293 22029145
137 3153931
779 18152416
138 71269877
771 18571599
3 51578602
525 673571020
481 10827500
769 62279107
53 253239879
768 967894381
31 59583272
104 1000000000
39 414415691
466 1000000000
110 12808962
751 20891071
394 82365908
77 1000000000
596 180330116
253 1000000000
837 287217305
848 214948010
540 203574307
557 58413203
384 438641005
339 68869103
707 66311639
588 553444864
772 92551747
775 105317834
667 338413735
876 255261557
431 20925980
419 25677595
330 1000000000
780 12956939
699 83118852
879 530676927
835 62271682
860 262941436
792 313260956
571 129844536
715 92545508
60 940583169
708 111221831
840 60824022
531 426433115
893 1000000000
297 16669830
364 227936912
908 248447694
54 839552790
726 1000000000
1 491036628
893 636440539
647 212345808
123 378680270
639 33899256
279 197727002
536 18247527
673 48351896
548 442084727
280 101918098
930 827413234
6 138263951
722 59172654
82 629621157
204 43768811
588 17074301
704 729202474
876 1000000000
590 1000000000
155 169064363
894 124076018
463 6846131
609 270978642
161 126720549
597 43080865
273 8779464
259 3681056
664 33309502
652 39955332
76 91712705
814 651495521
231 40552659
771 814985233
295 75083469
705 1000000000
574 4719225
322 132329314
355 114251473
269 337794181
134 45557143
722 268087666
326 50329042
289 1000000000
269 514459217
153 202117337
874 65497820
116 308030859
405 39198584
498 101738536
54 325512187
889 50190776
629 685099624
458 169279019
467 42821977
125 506580343
30 80244728
130 717216913
143 1621315
130 75060944
815 420001198
123 89172548
4 84517559
143 180349415
448 37576180
20 179562026
513 352318178
476 61123891
225 433653411
230 81839298
167 206883355
265 81402716
370 234056942
751 155050987
44 79796153
599 429524972
300 87831595
97 909841976
242 253452054
213 168888588
678 46992
955 192880523
1000 374822116
499 71467856
392 66140181
181 761946
815 61503654
417 6285781
51 93136792
896 154216130
413 10526535
232 294351375
342 92148347
579 189385668
156 230603161
647 1000000000
193 439911168
758 116832250
83 54305226
606 51423632
380 1000000000
561 176145108
563 45900580
134 461207232
167 144331974
741 153872207
226 1000000000
757 87498097
67 225236795
520 1000000000
274 16641817
781 811517302
567 155689244
652 7255960
738 83644725
357 86010342
75 353689915
881 275981298
43 139234709
214 8499853
912 592930919
773 136256402
715 72100357
359 39517676
573 41727949
650 1000000000
684 48509408
72 133229936
122 23216072
15 211440619
261 112941043
681 121378101
199 54151841
772 223641083
158 548973995
882 435550218
932 254422725
282 10769883
24 3945735
28 1000000000
490 28645345
976 3115781
298 5644348
406 275223513
704 1000000000
174 190732880
508 269478420
880 65002395
310 331448245
396 98710582
630 111249876
226 525047808
805 51064791
539 4386345
873 31239495
813 62095219
835 22062637
569 63836547
124 235786829
1000 5428096
234 496128330
424 6901616
407 60007155
19 146924474
906 14679608
8 262832512
698 1000000000
375 12855317
721 76650005
55 339290941
502 93428046
538 338984420
145 90135893
191 4864325
978 43300945
350 285627983
649 1000000000
863 330051305
102 5166050
602 51805919
161 1000000000
935 252962839
986 88484474
367 79989675
626 152226616
672 45254622
535 624033158
147 245591468
818 386285598
281 1000000000
404 7201193
656 135224374
467 103845650
546 5814012
713 168916172
446 419695460
413 329680969
339 9079635
350 34148318
211 288061469
462 170761486
901 312315878
732 81638460
721 194879511
880 202287848
111 49647278
738 127135314
55 267755343
458 100300359
289 178649221
600 248355457
429 262931991
948 671311269
291 25715597
454 197999649
131 53584160
183 1000000000
581 147777116
661 4284132
522 115754102
625 689315522
384 45286852
444 1000000000
537 39303398
156 33984445
723 199840351
107 40407786
600 1000000000
136 216098071
87 154793567
922 52490730
79 50905471
779 9381934
490 1000000000
330 26898640
487 513389985
711 49208346
982 10988242
706 157157018
231 94950052
691 381809249
762 355807697
210 373755018
375 55712188
487 113400613
574 72173248
50 3439396
688 42592770
579 825547927
859 635272301
35 298971655
456 360963141
1000 1000000000
608 96857884
308 109178802
129 55230590
909 2273144
253 44121830
93 1000000000
770 79022824
538 181593010
26 152980704
78 65862039
492 113932856
448 196044756
384 1000000000
856 64566760
333 1000000000
950 704392065
221 294910264
410 116809140
511 385590482
348 480640247
819 1000000000
396 746115690
666 19008007
290 8956332
66 36888255
414 122788446
732 36779488
704 619753890
360 604654228
689 202035566
895 51610379
327 1000000000
311 77352867
100 120736202
818 1000000000
750 135392984
998 75451686
655 323571072
93 233977717
949 188963289
749 566410672
298 184046720
112 37399025
445 98576961
789 301139923
846 24094650
60 366267910
653 495774451
285 1000000000
786 118848004
408 18416199
61 24264464
549 157541888
486 261891148
756 162337061
829 240840468
565 467332249
658 157857810
336 60064740
93 11161405
830 315049649
375 1000000000
85 63459748
542 215186801
998 656407534
611 220575984
82 1000000000
775 12156362
184 21940592
497 847698545
623 107431557
144 1000000000
401 86231337
926 18598475
901 8141775
314 1000000000
562 624114475
820 175902309
162 125897773
75 61802421
948 72205360
969 87617091
104 27389581
869 162671053
790 256163356
728 176934588
926 101369499
320 367642598
705 248044460
230 262603906
381 355356463
898 6294926
243 458913397
37 1580127
267 100108878
837 57304647
918 283213956
675 448807396
194 17578495
544 1000000000
561 321314420
979 17699972
874 215111458
259 127256526
996 1183969
234 75178455
457 51332815
879 16540738
816 133281881
881 1000000000
585 7107712
282 99959074
820 895408132
425 548872060
233 289688508
494 362752111
56 394706521
81 339183527
609 478999732
443 169833474
852 144352803
410 1000000000
65 1000000000
815 147425728
201 20224271
442 131456375
954 48114475
604 287926855
925 73481014
827 22772776
411 151002412
241 68796354
762 21798709
740 72608439
740 67759694
806 228132967
720 210565652
414 129470297
101 72401759
412 359690400
637 24806660
823 43691517
463 126115562
801 232355195
507 1000000000
17 61515113
545 210179656
687 31747520
929 321013737
435 27899502
219 428812394
774 67046402
463 49549587
6 910595893
542 357902552
148 81799003
334 99174040
320 244038141
200 106169043
635 415724526
245 656976433
371 110708876
899 337225793
986 55101775
876 368402376
798 93789119
526 77297842
497 177743757
267 24296692
674 166992440
346 169948190
160 174773351
531 319198005
693 243311597
94 518894490
856 306198376
562 417534838
153 1000000000
577 93213168
400 50591879
659 543674565
237 1000000000
502 592959117
584 220488637
747 723208478
82 435263281
506 338219115
113 166059970
75 119779660
366 9325421
359 149069546
466 547050736
908 118638546
275 246184690
116 4645403
315 7651510
645 237690152
728 39572766
561 1000000000
556 271003032
407 381393018
846 116135110
302 1000000000
373 877653197
168 349107212
67 555284172
508 675362947
359 307711160
226 452449502
497 493621662
978 43441298
633 56860684
788 996949265
319 297226046
120 396323015
139 917467957
846 1000000000
134 1000000000
358 15003635
766 6797841
57 523368741
100 11898388
821 355003307
825 24643380
460 74413002
227 6795865
492 379921214
772 21838482
527 69270710
938 130653625
91 122784474
47 1820749
130 886922676
82 19794232
635 56860576
458 281528139
365 86123643
249 233069610
738 341477047
958 197021865
841 7682391
185 482624046
138 60470405
402 1736301
429 1000000000
305 13566141
954 324798105
118 58100337
66 82303182
545 643899872
667 2033348
91 656471052
174 137447818
698 102041818
316 121859842
968 243624498
395 7446026
611 114847939
172 132260938
156 156878983
736 141126593
212 102500081
534 539773167
218 9804102
5 13571395
597 524994612
407 309409400
55 46631466
771 103981
359 87422075
177 52182766
637 126709810
721 184317840
665 916398802
19 47526191
595 86570452
903 362822887
651 132140870
973 177774815
17 25262960
5 104062958
821 1000000000
311 220646262
312 272735106
988 213745637
496 6850592
546 2069173
390 1000000000
266 569274297
315 1000000000
421 230343062
901 36514861
41 160553519
686 261936859
648 1000000000
69 160166570
145 734304583
401 788115682
347 1000000000
820 775583443
784 14520330
301 151970426
663 257063889
628 1000000000
360 1000000000
993 985547334
179 48084178
748 200606082
752 47587300
557 163186659
111 170060851
892 39128743
640 313321020
457 90268075
996 221931381
141 290845718
361 167739262
766 64148296
296 1000000000
941 1000000000
890 22341870
595 17158634
229 219569329
654 1000000000
507 1000000000
640 47111428
490 17946818
24 148935179
668 50336837
941 105200
352 376736345
785 23089977
238 1000000000
531 747404715
846 82990649
715 338730434
328 423174843
761 295307486
156 25923359
845 42866001
226 52425808
711 184049683
74 119446289
151 27691153
716 41391292
877 431056019
344 167432809
234 125733251
518 3117901
916 178107400
975 543319
196 373011368
225 671293987
587 42953556
342 196055746
319 106638238
628 75138339
34 17725
813 384907508
138 1000000000
496 319120247
873 12188311
852 245430432
542 321739679
203 2357429
441 37543575
620 4496689
986 1000000000
807 378817205
33 855184311
76 1000000000
942 112411227
235 485449565
881 318894847
124 595906741
338 1000000000
279 137654628
641 51105468
117 479617867
590 38521180
220 353989435
138 59617005
77 768900692
27 1000000000
873 385264307
323 40582615
190 806266307
264 186703301
438 190988282
380 985041866
727 334765357
749 373647883
403 113420623
869 118462003
577 11015483
51 228896967
961 171871664
919 195450880
538 3519318
713 68511760
238 906510101
209 6509716
84 313383219
871 34071200
932 32612649
955 86173289
375 691199301
629 859361421
635 89946436
485 548638215
345 184525642
691 164634941
961 73508635
832 648278054
732 703465759
826 307917311
96 191915633
491 1000000000
767 139340659
841 150485393
527 240892763
254 1000000000
306 817100551
648 1000000000
926 12993638
41 125281346
357 1000000000
568 7843467
790 1000000000
277 150020116
993 190930145
768 114279331
182 31541114
769 195376066
869 675025706
544 8520153
710 277489918
933 109810429
497 102630164
648 97792335
854 45745973
337 149714900
237 273108803
944 800512800
383 396111
830 446232867
698 337771244
193 209861292
735 1000000000
306 843848228
759 77594385
130 164178808
1 34266837
96 357098785
132 230783272
667 165582020
866 100677974
797 229535363
130 5227421
549 29010675
843 927051237
235 851135998
935 264946818
998 427797211
309 24489791
256 543660734
669 42711101
544 357353643
191 532181206
271 115462692
971 235802832
955 15199253
218 337030868
109 1000000000
514 302585207
37 556877935
596 14478098
244 78573800
760 50289514
744 89646671
799 313520809
842 92877106
271 166237604
27 359734408
530 478022185
697 163152966
263 64810415
118 50700715
37 374346545
425 417713569
254 29677968
402 266855078
489 377634160
136 129812925
286 321748030
21 351101539
533 6904129
56 107682030
14 92894265
521 60992477
737 2592104
136 1000000000
598 173791848
238 234523610
757 493661118
337 311490271
454 130101090
834 272469972
897 475475361
361 158050718
847 140006441
655 61893305
902 602186080
946 4193848
512 305205214
164 349162522
675 209551763
115 278762652
489 28351403
713 33696252
953 52718005
981 182489044
818 258899532
471 864801158
550 136226640
390 187418855
708 449126133
372 1000000000
812 488669532
120 62575439
454 142511386
674 57165959
954 82912397
626 85184063
176 392596846
577 16840292
304 1000000000
5 182781267
147 63900042
591 231011976
879 328866145
551 1000000000
357 413882474
478 336617632
182 1000000000
466 164676921
448 550376632
885 523677314
725 41024638
405 60345122
691 1000000000
676 520666331
700 569323829
33 21985912
551 647396
195 546791740
116 863528800
916 1000000000
754 175237158
571 188981090
731 50167678
32 445789
638 950688451
579 106117422
971 106300863
116 1098117
243 306569733
547 449255282
684 237608723
785 346942561
319 2540332
676 8166212
996 196731692
29 968013423
668 168965660
933 2275223
749 10823498
362 601884638
921 159671487
598 13768291
30 179279970
743 47505942
94 398946188
399 64820737
815 90581800
829 390081555
147 343998246
992 18361636
25 45847666
290 45805063
241 761369920
426 286543029
819 25077714
752 1000000000
503 117504709
460 225742138
149 26019030
182 79738096
893 178781257
246 257445269
943 14947080
789 433774365
763 38295595
209 66791291
794 243243595
187 152428731
466 213049349
148 1000000000
21 33178940
170 128769250
825 456250295
607 77860527
568 509160814
417 32290212
208 35734120
242 96928583
403 326721276
673 190954747
928 1000000000
613 34664433
310 387012349
592 313667210
871 403825816
361 36011568
530 133503132
608 64966258
687 441628994
325 7308842
702 106600266
976 7432209
799 334563958
193 1031646
867 311401446
696 37474173
328 114282406
662 907451706
399 41369128
33 48445775
33 162642566
122 8609127
740 1000000000
922 202683487
425 94051127
511 1000000000
641 1647201
219 92970886
243 405317458
325 103276651
182 593896978
252 129524384
924 23386826
218 156707351
956 210364422
358 61383270
430 19528594
856 53938179
938 37078176
928 228932940
648 13986470
918 567723615
208 160450117
866 241131951
842 92072552
924 5363042
966 36363096
924 64023256
188 7001581
379 374675472
309 1000000000
639 91120872
991 332591521
881 85665441
243 111788566
674 14614335
122 331256083
80 269048716
810 206614695
5 14247262
85 345092874
480 53162320
938 47874434
240 1000000000
784 452316279
271 236330970
249 110886072
300 129347615
788 320133065
743 13140850
817 90967796
72 96066490
16 156128900
127 357811902
633 675424
196 170337620
564 223154728
239 55660891
305 253596490
264 430944898
801 10155697
184 137977262
898 389281283
221 565034463
141 1000000000
312 732306871
3 150396048
266 150654393
282 271096247
41 358092136
556 307492827
239 311146204
999 219559603
499 107457161
429 165524413
948 19361771
157 26290396
540 9524656
239 189358272
466 42237249
851 80699094
974 643158277
880 1000000000
144 8471920
48 421835129
192 221459027
51 122523481
678 715116515
119 130695928
506 74707363
133 255442375
148 546391253
5 56681771
236 107201253
295 4351243
451 139308697
956 582438012
399 138065516
530 32429969
754 1000000000
651 53516057
538 63457434
693 251665536
177 510031
690 26142157
717 104609422
401 654891432
488 37513766
105 31838745
505 131750893
820 20638791
184 170105696
697 163956604
629 160178231
224 1000000000
216 753912483
857 82007711
937 17171347
340 299608500
968 150615712
241 20125291
325 574836462
608 1000000000
864 266000033
698 628250418
937 621647824
45 344512584
249 45640452
66 971718
78 130302339
570 73619310
674 628798960
11 356517747
867 1000000000
471 270052863
179 237524018
708 138530158
520 60378709
732 47537129
436 1000000000
526 77360790
302 17099480
106 49961368
830 1426968
975 462332534
708 143629093
407 829521758
576 927664930
985 1000000000
282 29933193
197 58389899
898 142361465
907 185011977
432 209939694
900 215390055
540 32295946
182 26843134
326 4142869
258 208515916
255 650009566
137 688736359
325 273977234
265 232990698
106 199072
508 341424814
124 80732157
568 89947259
861 1000000000
703 220553644
771 3953248
447 250816355
968 421516696
474 253103118
603 409543738
175 90900713
172 20198880
142 33993428
675 103834672
399 438073815
599 111651493
26 128221901
394 32121458
119 1000000000
644 324166784
726 175915157
459 1000000000
791 250315580
712 37806513
618 108688878
883 143346362
792 1000000000
909 1000000000
271 200796186
756 365002243
768 149293826
393 172945127
772 471629676
413 70050553
321 880419798
15 373473055
369 81215588
934 648058706
507 1000000000
372 846871
111 1000000000
296 169443433
124 28036899
458 1000000000
92 659327895
297 35798351
326 1000000000
671 234021839
10 381594385
371 73392800
944 18600670
333 105966021
744 162995133
598 470766747
786 3737306
860 188464403
151 88818633
376 7172511
525 1000000000
130 1000000000
405 377829828
739 140390427
488 381711095
345 59378768
500 232845551
270 388785617
91 83796689
600 992338011
764 31333600
545 70116274
838 1000000000
440 444786145
779 1000000000
749 438882285
346 400367537
671 109489025
843 1000000000
1000 115765139
782 104706378
671 81791892
987 395850959
196 190124876
994 1000000000
999 175233271
675 4067181
217 538244991
750 725405521
352 1000000000
275 220209776
565 949725416
874 373007557
856 1000000000
940 140512499
482 66353018
111 222430494
385 411706423
189 90085992
247 554880673
580 1000000000
18 207856247
822 78845365
396 132489715
554 162600520
164 29263664
231 205945968
122 97877862
967 41926907
581 140369861
665 95480708
455 40352524
269 122879345
383 26498257
315 138312910
229 880038938
683 88140648
33 225620555
309 190318343
715 100471991
825 64740124
724 287838895
120 34044853
378 66001022
904 922861
374 111477979
802 301480749
777 369337574
591 10745454
937 277123529
773 97590732
64 193894694
726 542046540
428 305219343
128 75427605
695 558386534
493 403375715
64 66620699
988 29746454
806 981571390
965 821819191
915 1000000000
111 580998
814 88666256
612 152202185
671 470075723
371 326053263
534 49239308
748 931671020
987 391903677
80 458626428
790 422625232
429 230964710
456 208507178
660 135561318
951 164609729
957 175622897
772 182115094
745 15966168
872 184524949
54 17787841
561 1000000000
166 149113893
985 41958513
79 95312200
102 43839394
835 95517294
442 26401180
48 377294845
164 109637196
344 52347194
171 1000000000
74 85772537
601 60709045
966 149417647
445 1000000000
92 1000000000
327 187244582
492 103930886
935 145026205
878 26741121
53 617259758
234 211301071
497 382379008
112 285921741
956 266312162
552 1000000000
772 701011038
731 480119175
722 689764114
55 162506266
727 248872369
998 179481700
865 297437942
326 199095291
282 106199422
857 514128363
392 96884597
213 95588373
53 261633045
868 399351711
711 29482748
853 130942329
768 596865053
599 320024
559 10639155
372 490077238
492 1000000000
355 191101498
215 826004802
860 361450923
776 619487778
103 342358682
927 8524210
340 1000000000
380 1000000000
900 287448136
143 97056849
141 8347231
761 223261777
648 1000000000
336 40803296
21 457070144
661 158375826
677 7075254
137 245294856
374 648216487
50 309598184
538 659164092
18 60866088
896 381578945
624 15057830
135 24426667
243 419250850
297 359075
469 265544049
13 193225138
989 98941970
443 1000000000
11 76521413
299 29311766
967 494146284
109 406479370
625 65434648
705 640127776
473 68174483
375 12642855
447 311031018
655 129952024
851 138598164
841 1000000000
454 188047106
278 391789718
254 11132286
212 625873911
908 234242824
644 54510819
713 140437335
767 336204899
563 527068856
379 13041418
804 52037706
450 53694081
507 226651943
347 35715646
727 174777577
509 35529896
402 2851271
290 85698612
243 848946567
401 360404826
74 16465447
834 256438667
799 80420010
709 17830654
506 129582294
562 48548672
171 1000000000
689 37988071
242 4413955
154 41181697
359 22408003
606 203953121
779 1000000000
451 10214490
532 269921747
578 215733109
67 1000000000
756 163638940
817 20412597
783 191620520
620 34476297
549 158749611
582 535585849
468 211671482
766 70925039
934 935558058
715 222082578
330 591592789
863 45484710
520 6138736
113 94902283
240 94577413
985 153001201
569 187149911
775 98652893
861 281784088
443 87095761
508 191520337
933 680760
124 1000000000
341 429198366
30 864039503
899 683778417
834 44358148
807 59623620
224 289996304
570 755976844
25 505702824
626 721297946
219 124248806
929 184072776
304 1000000000
877 66780166
486 3356413
752 142877555
423 389527237
472 135792924
906 143408864
631 444090997
790 161643016
980 1000000000
381 153503906
951 175246722
70 338232959
800 97730837
961 424296098
703 65220876
22 604138505
708 1000000000
21 1000000000
223 366716828
462 5919280
304 122005221
601 279632775
303 63328586
646 235695957
468 453320706
414 83367365
680 876019117
927 292800776
985 1000000000
779 85118504
305 1000000000
360 730263312
990 293732274
616 26942532
794 40199908
169 36894705
395 152205068
853 105395781
515 156495145
35 28640465
889 1000000000
906 47847368
445 297411589
164 336373186
791 4704310
288 305954901
999 24012324
358 100615397
261 21242714
894 23874766
649 159541867
904 1000000000
763 135148436
989 1000000000
299 346972801
155 42793921
489 8628165
187 48529253
966 24302927
6 1000000000
584 1000000000
570 280803298
248 51163121
960 618264730
767 255277857
665 1000000000
308 11929788
236 15136473
790 589827962
768 50853894
527 1288712
351 91068590
870 649874573
360 37301163
595 3003701
731 848029848
341 1000000000
376 32758344
198 288886234
991 98147357
773 11637723
128 236927369
515 21890472
795 4300773
278 123713754
960 1000000000
615 806956815
679 60649070
878 455500804
617 727887752
428 7553523
508 138197305
255 1000000000
305 211582823
720 501711751
441 385088836
224 190401815
762 381354224
926 193296171
830 1000000000
977 1000000000
740 77775082
539 43028788
204 31978054
675 53365241
597 4024649
192 480704567
9 388764743
548 385836668
303 172918342
670 107440484
671 124702057
710 98329926
193 87792770
396 1000000000
213 307011215
753 240106261
483 664470090
259 170242917
940 48589597
235 260630788
398 24223876
193 154192
706 488334407
70 132298728
185 111839618
608 91422912
393 115499826
153 129387457
940 434918044
511 2618203
768 27869300
732 79074909
687 945422583
479 24936595
896 84654117
136 38294087
867 1000000000
294 222010984
536 689548486
259 1000000000
703 325752193
950 748465727
864 400413732
511 120557259
539 697770623
414 780578388
216 151266723
300 1000000000
15 211664938
31 18900394
512 1000000000
184 102394449
219 328827158
391 165691739
465 409676073
149 140972756
280 1000000000
320 1000000000
810 134251527
458 101974674
901 168034928
345 36455997
243 173115815
591 8831467
75 404211445
155 799472571
788 83912220
468 435944332
728 22167381
12 25490882
206 90231010
314 65229254
390 81027762
38 82563934
200 342328815
160 66497992
44 342567768
544 440627
562 19532707
134 228898349
146 1000000000
587 702990169
709 792766177
453 11045929
593 46680155
125 74303828
119 969125538
420 231489528
856 63224256
480 322704244
954 562753961
675 708398779
95 151250399
755 154616416
621 18171397
538 30113842
326 66839321
223 237995923
329 24543299
345 779126701
102 1000000000
658 124919506
620 43730932
537 6025558
629 309085997
398 34522280
592 176562104
809 846635780
877 840008221
826 188906266
109 451536955
993 21285436
326 304022187
679 219140516
465 1000000000
738 726265922
702 684463982
83 24856729
606 7652482
155 867046519
743 304482600
976 23472228
795 182839487
692 17190695
496 295019637
637 254666306
168 40659735
197 30464874
849 299422140
123 1000000000
709 1000000000
358 425820120
115 223095503
448 164283664
547 4527175
312 674637639
301 768027550
526 85842358
633 360588227
482 185978514
743 242926174
244 52395280
335 1000000000
860 121968993
105 112572048
426 168571781
349 149932265
535 1000000000
892 92691413
265 1000000000
268 781534848
674 234564985
766 23028917
424 178850842
403 210174605
340 850598572
810 61783250
391 1000000000
130 1000000000
1000 1922476
661 467094389
526 33698617
474 509862328
571 743287980
352 1000000000
390 276822248
169 218020786
663 283734099
44 72895797
406 905437153
257 394758533
707 190155919
688 409733
774 38551564
497 106354931
783 70795475
421 102525954
454 260477610
90 257319053
156 16779564
17 62848578
191 215357036
10 16858026
760 566688894
86 247459813
424 498155
675 197362897
853 307182825
915 31813449
249 623895919
781 28487999
595 222760496
352 39713889
554 130569244
134 98815714
152 100558176
46 61704987
604 87197025
824 92193983
326 181740542
412 11993881
142 1158913
50 298780011
28 197718723
530 248569335
944 36169183
796 73609387
858 1000000000
400 185278774
322 56418985
582 48061512
945 1260690
383 122093002
573 99000204
273 234682376
839 55430328
141 6693270
280 211736516
412 1000000000
398 96732048
708 1000000000
155 182052492
407 791659621
950 9543603
580 67509048
318 98443929
202 367412124
373 1000000000
907 123123355
570 57918314
950 694887603
261 1000000000
107 602248370
598 130647147
906 170814526
309 103527789
667 271668991
434 82434526
246 96793178
485 15818449
323 1000000000
494 29008278
371 803636707
478 281043213
804 114985541
947 249870501
567 1065878
470 116651360
485 43703129
336 215125148
684 319739774
951 135379743
446 346780279
685 9240344
265 1000000000
1000 610321
591 473723109
778 193554378
655 542802755
138 780296183
225 107842640
80 1000000000
52 262230144
140 35106391
626 557655934
982 9368401
570 75261259
14 2536222
476 40644952
900 761707873
689 716646600
496 1000000000
487 49491777
490 38851686
719 16787148
794 1000000000
521 6656862
593 16244449
230 111399316
821 530804583
340 5862059
944 168455011
229 144071009
552 24902239
527 46133315
87 121774122
524 520568017
715 42215606
282 175524865
830 520223776
3 26246482
855 72395235
62 416485211
574 53997487
339 1000000000
59 68434923
114 1000000000
406 419840653
555 485905350
583 105296416
758 2380381
830 263580773
771 13892576
43 12324776
58 226672199
406 583307515
507 40010548
479 370274100
759 25307409
935 1000000000
548 15421003
188 23057791
44 356213627
832 549353866
405 60836526
585 934151936
233 765316980
209 147481942
310 144972156
14 426159848
494 875893170
898 324326930
488 16315358
956 674271474
555 20247721
876 1284412
761 262017816
306 123589824
441 41399866
653 72699035
219 60266458
864 163021190
7 175377015
912 230645917
53 1000000000
606 352745290
838 266330168
546 1000000000
168 26780146
284 53352795
68 61475767
61 1272825
27 952057998
931 252544083
459 1000000000
919 163984834
669 220946040
570 87537499
362 216605821
187 450243103
921 0
241 410302222
465 51983064
878 166153830
20 1000000000
601 104489570
17 283180979
666 228862192
104 432286489
768 58757468
393 151953013
21 171983873
108 156193293
472 137348703
153 818342010
778 1000000000
16 1000000000
937 299450498
953 359159283
358 148237459
580 18695590
337 71900603
826 119621950
162 1000000000
601 167590677
626 385481086
858 366978156
855 1000000000
70 24498962
795 1000000000
371 315957029
100 1089980
587 179032291
860 195402384
669 7603310
594 62254010
96 1000000000
382 1000000000
534 422021739
591 885177299
246 327587998
983 11942016
904 135860446
101 9010724
236 143142616
385 106740479
730 10839824
779 71531317
690 221837210
244 1000000000
668 155677043
282 43525518
289 1000000000
750 112068273
951 102887626
928 312350732
823 150728134
881 79747516
818 211943761
695 10045815
238 81305865
916 19758663
365 314677146
230 21079006
813 32434952
399 1000000000
288 61378078
718 128705586
613 141385229
35 3854636
852 18497857
501 645913001
37 55553745
590 1000000000
583 241669361
565 371639795
308 567585702
706 189136908
940 56897919
453 167821817
565 179040000
423 607819551
432 57866964
534 1000000000
885 149462127
483 34894610
524 120384205
438 72322312
358 49422045
544 33425873
881 228969361
279 898062817
431 87085007
725 142410479
950 1000000000
576 227823979
360 60501240
282 538763041
820 214192103
330 297290536
833 68753213
343 382016031
921 37685888
827 152402476
779 185616648
349 10718290
655 87270573
917 136449130
333 38781040
763 35271747
429 1049743
719 107781727
983 83731161
841 46782643
315 88289670
26 192947261
746 25000649
40 302774339
794 5593787
636 166897145
180 596773221
679 42163032
913 1000000000
47 333445862
831 138603026
998 1000000000
680 166369372
298 9555279
66 195021850
845 40169183
983 1842225
238 182396519
958 122642539
660 188125440
951 99733762
801 154348212
561 67988379
724 73879297
798 1000000000
653 121633319
981 137191191
580 32382502
750 1412052
217 199321015
929 146890875
428 32843735
215 40082543
302 12598003
326 339178715
301 162013731
479 46912820
594 6813035
971 80169046
942 258561137
864 2845452
919 199386376
664 478008091
319 26177477
913 95118485
412 465976672
389 316487136
552 444560737
930 292706325
513 83537231
266 115390448
193 318717451
644 183028598
607 1000000000
592 77489046
331 13744770
454 552844606
589 85234250
910 30527586
245 164437874
432 1000000000
699 11085904
420 1000000000
439 163214114
794 65191337
921 104342266
986 263541235
618 27517912
613 34389240
88 230442523
49 395881446
948 281730791
127 333061311
343 211655764
192 1000000000
687 111403474
410 13317145
398 283605183
767 1000000000
147 272149072
742 180255099
989 29956780
831 73727325
54 1000000000
969 13510718
205 146005180
630 24136510
250 107315380
357 34920194
597 345700034
982 565834845
102 82994638
945 258801325
445 190533003
774 112630544
42 1000000000
302 69693761
749 227067863
271 23968895
871 424097574
594 13200997
478 261162006
159 503659416
195 31199965
871 39819088
143 6620053
488 1582893
488 192146348
428 136905379
896 1000000000
298 153931758
214 24027578
857 9112509
489 220867996
451 41439826
115 1643582
367 820368233
459 559966093
357 259890286
33 252765048
621 258300784
989 284774086
439 119743617
631 642690026
35 44362932
111 76839093
177 100763536
45 170416753
721 463772786
281 799635650
787 84597405
540 151741915
215 1000000000
388 361120689
198 3643342
610 5628787
126 216214080
623 407622891
17 515206702
89 13687772
461 1000000000
266 49826218
516 17419395
401 211944435
805 263056474
733 76969998
775 90426689
592 12251443
996 4430627
833 180061135
555 43946338
264 80066731
548 29225717
981 1000000000
447 399623960
8 11468481
348 51940209
697 350831481
699 279392894
816 49770141
548 998719382
909 236045680
568 436026949
424 131744103
205 16050995
74 390382160
180 1493238
841 166462684
926 157694622
175 38153072
217 281629965
426 622566269
775 9574576
796 314483033
398 137412942
787 806268649
712 447158021
361 1000000000
444 118844729
373 7964166
26 988618773
711 204989994
681 59259671
439 50036763
275 253027792
645 13666085
807 53877392
881 91450275
437 564118358
707 765089141
390 1000000000
411 239200152
200 588190422
745 162773174
68 8500677
605 53947642
74 52543326
424 260713228
803 350628675
88 7549136
973 1000000000
111 57323720
122 1000000000
179 247977999
952 1000000000
806 130609505
761 496860987
990 429457294
499 13940261
397 276946756
48 44646924
754 378739566
279 55143771
165 816207589
72 26931866
518 144921819
859 78872927
213 197463698
472 15468506
642 366616390
767 234560071
101 56922595
792 373479955
502 16490880
227 78097262
285 8607333
456 94652206
106 297119221
912 94116013
214 10675624
193 175894757
711 57049855
101 18047821
623 19812654
26 16172518
228 7156353
706 668189305
968 289638189
867 255824385
409 275464181
919 658516477
825 1000000000
61 171805753
719 13357554
796 1000000000
819 132966924
566 1575049
236 229232803
906 60423428
628 69493671
256 70914980
690 686123712
488 40318527
183 98512827
2 856704145
217 130085411
431 120114459
921 872362839
5 31475592
623 899297380
269 1000000000
996 920323033
807 1000000000
582 236859873
284 716013525
14 152744439
410 745054457
501 799078472
75 232190743
602 9447394
302 498408350
268 5505761
354 316719702
317 161097212
745 1083590
12 755417468
730 1000000000
265 132783091
981 104603243
483 613191526
314 81009340
836 678082078
25 1000000000
947 146651916
746 1000000000
360 1000000000
741 129982283
572 405788641
738 975058376
77 128882955
769 332161609
980 768789043
267 163187263
97 502745382
158 1000000000
421 1000000000
307 98108610
798 86182996
67 561913631
174 179695514
20 1000000000
531 55044061
40 133649167
703 6633632
718 48185437
985 300153188
37 500175437
81 352592785
399 874049013
622 10100457
59 273118214
50 1000000000
57 108563829
868 281855263
745 99335642
676 12883318
843 249771208
18 114052989
119 18454367
311 18000378
357 57393624
609 268190337
318 451301420
177 472396148
440 276359733
175 367371842
28 62450214
388 39563257
411 186194795
806 34229508
683 106144232
983 140219782
126 56175432
237 1000000000
746 969694060
970 161264310
465 129119309
373 103547840
234 1000000000
38 1000000000
509 5557068
844 268656037
698 773511756
505 64923460
600 51791337
692 167395508
377 360001871
301 49909788
773 1000000000
500 182310701
162 136042667
681 499408503
705 391990372
61 372028419
66 29598468
430 54285903
589 108152459
149 662388199
403 150701761
403 287131327
898 1000000000
998 59408078
540 386893141
744 152264481
887 15086402
319 13139994
69 2732788
765 20493923
517 520074628
689 47194741
574 151153363
538 3115951
994 30785213
874 24546436
736 1000000000
944 468042174
328 278240003
964 141562269
330 385623564
790 109208534
830 250297099
606 753803402
228 143716288
124 831845009
868 35330112
697 321089630
374 41389343
155 286293032
147 7222898
675 611683488
857 459058138
354 21675200
466 356670286
622 330533938
860 209590325
361 187972565
665 106689187
601 123995563
79 307603247
376 785810689
912 619593368
549 23936308
691 4504657
487 37865553
743 780162323
160 140771254
382 70272089
247 1000000000
631 224652737
868 264473605
194 111587663
895 658647761
87 193371568
8 505977495
622 6312191
183 138984625
632 328342173
141 464178898
651 97369704
416 269530168
880 6316153
985 38601718
632 138231609
777 1000000000
825 94245575
990 178189304
948 1000000000
218 268364135
290 2077152
947 168604009
458 26545579
875 1000000000
955 227279999
800 81757846
247 102218576
996 37818641
677 426138684
430 58913666
117 175854629
190 14069217
335 409028925
676 59225901
523 366832910
232 83761401
553 1000000000
506 76419231
793 3706396
986 287209830
635 137686202
368 464641398
335 658296421
429 314179227
734 271168201
543 301465060
486 66207897
231 83018926
288 1000000000
214 1000000000
21 70472896
506 837431441
931 304669220
53 1000000000
676 256347261
846 28812363
487 126683630
716 332699534
644 48675183
673 62232807
866 59465528
28 208039306
363 1000000000
709 43090774
662 26624067
308 785301178
323 19724740
65 534429421
818 387874306
908 152497647
739 402129783
405 65726934
894 10318088
52 246016611
708 433653577
890 108396654
939 8534437
589 75353131
668 29976075
622 80589167
832 31215071
638 18446606
533 300434986
747 606181967
621 1000000000
975 123713072
94 5847457
33 1000000000
842 28349715
288 177820036
152 133851049
174 103382745
360 58026932
594 31550593
650 14775328
196 1822325
22 257466380
388 719305319
708 1000000000
554 3210471
284 255410928
574 1000000000
214 49525433
552 504490350
610 1086106
272 1000000000
624 76820838
847 150749907
136 84020280
515 50354617
875 340052077
157 66223261
279 435416910
142 28919890
286 204816074
556 52835902
62 1000000000
873 70951475
897 54930142
323 165917468
694 1000000000
364 725536834
692 94627081
235 254799274
37 440556473
624 75015312
48 336645916
107 831244430
469 247037230
660 349248396
932 115177979
99 54375665
221 9283425
704 53858433
40 166013373
675 2581702
757 4542779
508 1000000000
853 1000000000
299 314799387
878 971778360
9 169213265
313 753961
92 76273462
847 1000000000
510 163483106
734 54678254
413 147117288
96 1000000000
715 5846458
427 106318679
758 66366935
889 69167302
176 196005269
241 379204138
264 54219171
211 173580083
310 391483315
726 235781016
178 408027935
148 29482088
28 43514691
508 391071434
300 131840441
222 224675370
946 96470149
691 1000000000
150 416623886
985 194544828
200 1000000000
225 52823007
456 188055028
659 344087194
671 368330457
744 296556483
891 2358671
430 1000000000
758 74628472
911 1000000000
142 356552777
841 310751510
237 453415574
630 125925790
857 1000000000
332 54872049
148 565448799
765 527509681
509 421686033
168 1000000000
412 1000000000
149 16302111
825 515029720
628 184782942
12 1000000000
261 214473511
693 1000000000
416 60550003
572 174876736
621 63882095
617 103402677
780 122116069
532 1000000000
829 52417365
917 521472845
217 171205501
117 189145120
662 35703719
538 280391880
85 1000000000
765 60739589
263 48225378
775 192306365
835 220956505
903 253278387
1000 48391466
420 11255380
472 125706531
416 112059987
802 583502292
450 14330829
261 475217252
354 294727578
523 177102517
799 244011945
771 1000000000
787 138478636
5 437866398
685 101862688
561 141153399
734 207473196
671 39810935
20 55501783
176 252056171
792 43215212
930 436070109
410 58407284
46 395575298
899 309082541
4 91075635
257 395205426
53 81324489
205 110984770
671 590232
680 59730826
260 45167098
1 253843748
595 26559765
991 99073652
707 251772493
860 116053270
606 11075823
839 504037065
947 25882880
263 1000000000
154 1000000000
102 332311286
755 263170409
619 114852167
662 86999176
790 888744572
83 53726372
607 558068568
466 216450090
519 1000000000
683 506981401
916 26761895
518 108786410
959 12206881
196 1000000000
120 178721705
755 147160340
104 97803073
364 19916554
733 174913183
168 1000000000
977 1000000000
589 239258312
66 131786035
69 1000000000
258 61785376
263 841278994
696 113837347
922 5342352
308 1000000000
624 692540829
869 93992993
816 485117256
581 1000000000
554 477607136
115 2888509
62 298506479
855 601634933
420 819244746
889 1000000000
588 24463342
746 57886998
950 224308858
960 97099492
435 94616582
116 100748112
641 1000000000
662 773813863
465 1000000000
863 1000000000
468 383093718
101 333845776
512 257606098
34 54250431
975 292197154
948 175475053
79 226224562
957 90307964
106 1000000000
788 13835922
207 1000000000
456 30092711
358 416370599
859 140354030
47 167478815
276 312450695
625 292276585
891 80786909
142 1000000000
456 1000000000
397 76722960
683 1000000000
903 11530345
468 126238240
298 95153357
556 38915049
879 139367001
345 149659462
30 17519300
196 233321678
440 7001240
22 154425653
51 89378398
149 193150500
817 139908405
467 94089589
784 186451234
822 9595465
474 2660164
816 3221957
733 143357723
488 12674893
275 66776187
725 6980626
851 117652458
9 64758670
829 16091244
315 561085115
249 21714955
555 562275385
607 125873221
905 60373327
471 122534933
69 42373011
169 115980721
55 475484431
325 46679516
592 76347745
635 475188371
558 108564280
444 1000000000
2 42874356
438 55895878
325 33631006
339 121500967
37 177518077
25 255589625
252 983332718
690 22054702
8 364956437
884 219819780
875 1000000000
713 199726193
708 377606126
840 1000000000
810 1000000000
176 237125999
183 214613635
891 12264412
954 9335815
784 33882625
971 1000000000
103 211585427
698 1000000000
344 14004851
15 86121602
75 155906880
946 19330674
513 66384589
411 24972
80 249233421
779 1000000000
649 11271030
408 140769705
629 14962762
891 1000000000
418 244232492
877 298525165
561 306495330
396 28874762
659 18509400
474 17133167
975 106110059
846 287227824
132 1000000000
775 22750312
172 6261185
839 156839625
750 304009402
453 870351253
322 13865203
729 368124784
104 178242126
731 604716257
800 87398618
859 10671023
90 158930800
401 1000000000
550 160361457
413 66789110
908 137762892
823 483059255
588 254329347
704 661944420
175 45352757
694 1000000000
883 120086714
162 13229944
169 152788806
581 376376482
298 78848953
701 2143399
52 211458627
396 53624949
969 283034784
609 1000000000
416 412332195
699 32586958
360 61469309
428 723655
987 493583158
171 1000000000
344 534805393
912 18940858
527 440790661
859 1000000000
816 138286174
788 873486687
699 465555114
51 655189630
568 694523760
320 921583938
215 241994489
675 119944904
985 19199084
125 524102431
340 110293826
724 38497325
137 200440789
577 65794821
137 185583086
309 769909128
442 419635352
902 405451542
462 110550545
782 833692572
459 99555677
172 81834070
491 142342965
551 183351665
613 138211317
329 10847243
721 2848813
393 75826542
687 1000000000
951 153761818
183 88758220
219 1000000000
648 572787327
5 25098794
669 1000000000
357 155296636
67 37676321
787 455139939
451 34788730
503 462210
645 13371049
41 15662185
913 2774261
650 15673272
600 28137285
880 215284005
144 12661206
333 64046456
411 195302806
343 411671904
815 74929194
464 71257938
990 1000000000
574 1000000000
239 265619151
907 1000000000
785 181262331
678 24235233
118 1000000000
527 347138833
157 245137144
214 385197856
966 427589875
867 263307045
521 97105248
614 93506493
950 643821401
143 316284485
437 1000000000
822 138522666
598 185192705
83 1000000000
794 182993575
142 545108720
375 869745940
456 106545257
102 174052018
935 204228340
200 811498883
197 185089457
259 5677581
664 16146701
89 283988351
346 909733282
880 83724016
473 32689393
634 64263531
79 19490407
990 55854964
395 745925654
964 229634064
45 117293904
675 246094779
693 183133246
645 266866533
979 17669247
249 1000000000
447 191204310
799 828271696
753 1000000000
680 48415774
9 1000000000
906 57219475
39 9187319
62 175039817
627 499740343
420 59048982
142 160749148
837 307484380
462 1050748
911 803853432
957 102836935
836 489892685
721 29193190
82 32232678
180 90872218
451 304571584
940 1000000000
221 307408809
563 18107779
930 169181659
272 53396054
209 955223952
851 256027772
466 246229613
596 246782678
453 19853375
554 7827777
930 319197965
816 64255958
945 1000000000
427 1592171
682 25993276
500 24916619
861 1000000000
259 210110618
66 24457859
256 1000000000
186 131619100
260 37693537
403 56757078
389 579797508
430 74972586
916 123270473
28 79905142
114 175127782
484 539236
638 19959579
637 14293350
991 494415074
785 18515513
783 823279894
119 4418387
501 2694151
542 79553001
145 67675788
176 47067068
594 38659980
924 189685891
250 2074066
186 337230216
32 226461150
954 781859929
149 192019502
132 296001001
855 231721695
865 243061885
207 120978256
383 90391904
269 64206155
767 298702334
489 12760969
161 168175573
308 23191956
838 367596426
620 109438716
260 50979742
475 6718712
477 386793182
735 328309417
608 166609822
722 34607028
508 278696475
587 744066910
707 420887671
98 99164246
84 364839713
710 112877062
223 1000000000
329 38791982
588 221748001
250 1000000000
763 12658782
441 34812209
244 42178122
254 78937390
311 83956930
474 69208967
988 230534846
843 44819690
619 147194953
930 62621669
156 954693234
39 121138408
240 20743441
755 48492791
381 407093742
852 208771641
357 54518442
20 222613033
566 258509435
785 416018342
194 27523434
325 70094375
520 606531118
327 73572722
175 297159265
855 438993172
889 716139683
892 1000000000
149 61147826
872 256121745
323 166896344
594 54473382
251 17353424
482 1000000000
925 223844626
456 397546090
577 121961902
708 217170918
599 54963566
839 77364258
248 6203396
687 105836304
554 203779358
205 190057458
286 181891926
218 374150863
877 536701454
844 937918847
885 173176253
93 196574543
192 153190633
691 178145999
44 1000000000
856 1000000000
83 389000598
603 241721374
348 4577866
931 104598298
967 491541638
426 85022173
27 60362038
823 1000000000
490 90491978
866 773129477
731 80521686
603 138016083
406 1000000000
578 33060697
156 204710202
575 99618767
43 1000000000
603 39194692
876 2109585
68 376698097
759 591212493
51 25761994
333 158672709
169 561811302
244 292626927
716 19593932
918 676369714
582 57266123
537 198257165
333 808453991
983 1000000000
147 832737740
278 290922021
175 1000000000
968 1000000000
848 7401946
116 259468574
560 66162382
162 95208668
198 290553
690 265925385
618 6170051
452 211388355
28 542760633
184 445562331
276 501676574
246 65747942
994 521686039
790 448431859
247 484528040
360 422138340
425 182077740
941 1000000000
137 745090673
59 1000000000
616 41046347
396 81516108
948 203976456
334 91288218
463 61044750
539 217307190
127 15509795
169 1000000000
22 331586684
162 72639616
346 190696449
125 142202156
965 438475434
777 2882781
214 13456107
192 1000000000
997 30639569
513 157678875
178 16134659
116 1000000000
437 666551973
73 75604617
646 474319643
128 145016174
317 242630703
434 33121914
250 58208377
597 187759594
46 370958388
226 322846227
87 128049626
650 1000000000
766 447997746
571 246992078
436 52915942
462 609743682
583 505619932
556 382144184
593 15183463
332 116193342
985 1000000000
301 4008351
910 299689185
121 784475463
626 80212612
743 5487223
124 483927559
503 113278484
540 1000000000
801 37528720
106 67793767
965 169450093
902 184328961
763 311286937
840 177148279
739 156456585
568 16476445
829 384863132
790 42333470
425 28152235
739 1000000000
800 87146418
29 3240627
944 299814314
357 36942998
554 254392294
780 261593223
455 64087759
408 376133434
189 165600596
339 244422495
726 128734031
220 140743614
825 50894194
306 23641831
461 6021915
615 18089720
124 226435592
138 1000000000
789 220471935
403 592545284
776 55913633
266 187349632
973 145085600
335 311698293
652 307609642
362 6315934
533 409671280
499 941470668
656 32772162
890 61427436
222 180419663
464 73593365
245 1000000000
59 142069524
494 55189481
916 180654944
10 74566846
324 151308369
439 709575794
305 11114783
631 164067192
613 22949867
288 1000000000
231 297361487
804 7701937
342 9764193
738 64880198
612 3690
202 107467064
16 527850607
548 273184802
170 244425755
951 31077381
482 58103271
725 25507588
512 129296883
110 344349578
132 1000000000
776 243314232
814 72729553
332 134641373
230 107503411
986 28181064
916 4562372
58 10853858
105 269164524
141 70631176
603 248094583
161 67465193
172 80128493
232 80668345
626 42065877
232 31466654
623 165349105
723 79932344
169 646023463
840 11752124
58 401382544
78 22806960
937 303934755
679 874084
166 254527686
522 4681692
345 101398545
735 16239822
690 660351018
390 143495770
17 124137268
631 227765300
886 28530822
738 293297735
857 1000000000
871 88484293
10 377761585
582 230466851
305 721109165
192 45009627
567 202857408
755 108930416
818 1000000000
81 1000000000
548 1000000000
888 1000000000
499 1000000000
258 52886828
489 18274775
197 466806897
540 19653162
83 26797869
646 388659758
339 91375440
134 21650699
228 38810680
492 68258584
8 191318830
312 16536939
510 32563861
754 3577387
438 120240367
498 113225189
728 134505479
808 8506833
860 60793458
204 473273309
651 264695439
822 207670674
547 201610999
766 2267190
197 81791982
253 7071267
330 66318254
817 7343440
448 203300949
123 562787735
473 198240489
860 265664976
627 55909225
115 206188336
840 417325620
823 146465446
390 144267374
314 190035874
303 206895657
683 734052362
618 80487008
418 96240217
871 29925933
334 50773685
614 68986695
609 18384041
39 79533108
386 228543715
474 910043
514 116152326
887 41746600
607 151166279
838 34136773
498 88012225
295 241901852
915 44823891
51 119485032
491 40402870
112 209315897
960 196111470
487 282553061
579 600212636
553 48146429
37 120691232
284 156576077
245 383106026
570 54554306
898 103543084
562 1000000000
958 873765163
188 55972908
184 233110927
807 424254191
368 94499813
501 230659904
805 28496505
749 5529758
409 72360862
879 1000000000
579 219539094
339 23349479
27 19529304
785 78967915
986 197387734
897 15863917
726 15454931
532 63355556
856 1000000000
640 269680542
16 138524126
974 309118191
943 361026058
751 443283469
563 44715288
761 1000000000
878 12354875
326 189913205
982 1000000000
317 342453763
733 88888145
149 281527939
946 171434645
528 112214309
933 47240166
405 212349542
933 80208596
196 267140473
276 99117616
317 566670950
881 572295967
480 70987757
620 123689827
101 102786685
349 37648667
364 119270296
749 448054772
581 630744658
546 407136996
368 113523567
493 2363218
965 78679705
550 60590459
357 275966200
958 274284934
534 231555127
307 30389340
778 120945801
439 84013904
279 16458527
688 137550523
367 50694147
168 255029220
929 54567234
230 333660174
548 41528550
361 157945388
538 118941959
427 149818520
490 9849713
251 1000000000
148 239681627
393 495989610
88 59688435
181 126783672
830 97499645
319 5443329
958 1000000000
663 220180995
912 133888772
38 1000000000
653 684038053
146 97354514
899 1000000000
732 47898614
243 451052569
21 550603814
454 442473292
763 902848971
562 250263917
992 998695052
985 121670844
698 1000000000
225 67758469
363 33273050
396 300193143
770 476599351
313 64489101
118 114856728
104 1000000000
753 144616131
896 170198904
882 224897152
163 284140348
945 445260946
216 111266851
278 27145521
423 35753490
561 279730908
641 113117693
690 275105915
156 2301659
274 5396007
537 219359361
967 12272214
856 509070
386 109333550
690 468512303
740 523504240
29 155703097
451 181643280
483 1000000000
921 1000000000
610 1000000000
652 83480286
580 856605823
438 66710432
983 107776466
390 17785849
37 1000000000
323 20036468
629 55913352
559 12198824
255 459728631
713 1643409
755 172937951
73 184380242
761 1000000000
799 1000000000
721 734026778
147 5355270
347 78040965
837 132796014
327 228724354
678 322844218
421 241400552
52 38235985
86 136658996
16 48386030
128 228749687
867 308415496
412 527662811
883 789531461
691 46552004
202 1000000000
852 271634040
478 168357529
902 184132615
145 1000000000
747 253267654
497 232939608
546 1000000000
496 1000000000
898 478456686
149 208864093
357 165194558
656 160024432
706 422572343
897 84273600
985 145935295
232 116633398
658 1000000000
517 216015141
101 250467767
552 150060043
987 1000000000
337 77641575
386 110837580
209 98990367
763 276003973
622 80501898
494 129426613
41 29989855
500 51704815
651 536730319
139 53961278
578 56958495
917 258946047
64 266590918
169 38539533
476 335107674
174 31323080
669 75895341
662 182048624
133 38303467
728 24769193
59 220522098
260 154164841
351 157380384
858 422010015
665 1000000000
530 102741791
481 177368455
724 13697790
23 24492304
16 30534149
627 442944756
998 107449399
61 298418607
334 139289420
302 68490165
809 561416500
660 47541472
189 91496931
808 385642882
707 1995994
139 1000000000
284 450156383
35 175634752
894 67673291
138 259702863
259 98541246
199 85737061
370 89923926
481 863454061
994 421834253
890 423819536
861 311530267
129 519692502
570 622042790
374 100307662
409 233783901
745 190624995
986 12144346
98 236243974
181 30878041
649 75301134
930 561515977
30 1000000000
793 28226165
553 87626527
347 23411551
547 477718169
598 268438068
714 291991565
467 551155642
375 239165409
67 10687300
411 508994943
812 442430535
844 633366
856 157626266
548 437754613
597 260383661
561 210494264
773 16907348
973 285647180
191 548254931
863 101206888
987 333932520
471 1000000000
913 112338387
477 72941814
680 1000000000
457 83995106
138 124839668
715 239318336
214 1000000000
75 541963217
949 210446103
793 153172813
253 444738592
733 189871085
671 221937198
631 528566261
587 1000000000
744 547837295
186 9795814
662 162256753
642 1000000000
539 121274689
861 1000000000
453 68255295
505 197478615
542 1000000000
432 211616376
412 415293292
337 325505389
777 69787667
131 115406018
708 494449230
608 962326660
621 960135694
919 1000000000
812 553822199
992 428865773
321 413275871
531 54980186
868 276527602
488 110620769
981 558092867
279 457526768
900 343740050
216 265222175
137 103385465
259 164755394
996 159226165
865 17535130
310 1000000000
360 53305916
213 667309174
986 57732876
867 120294380
965 517514534
438 1000000000
579 41486398
392 217079916
274 160583708
135 44166144
724 7695668
709 155958438
280 112422205
833 540937
549 75668904
259 9433188
709 1000000000
459 279820712
527 1000000000
977 117156677
507 450895709
389 249658257
825 1000000000
903 23490789
177 7242145
351 164578576
900 138273946
213 1000000000
376 110139816
945 882365464
246 595326194
76 1000000000
39 296941160
44 410665
321 367220986
938 540317122
309 377426995
103 70968724
844 38238816
18 1000000000
693 273254206
770 246014663
895 34169637
641 344711252
268 1000000000
358 237208323
611 205728572
841 48344953
972 274043746
625 155280724
383 125845751
112 1000000000
324 302929420
925 63022486
963 147432194
921 325404790
620 9053130
586 26126302
143 78865885
169 88940600
804 287474261
534 45451644
340 85594278
546 579276537
45 431599431
331 155571924
64 24805544
674 80031622
350 1000000000
664 1000000000
77 222129563
459 250834297
167 46037434
317 512674069
163 237197704
173 349898878
112 165001277
755 221011659
744 41849564
790 61919397
82 412562339
120 38847350
46 79462703
192 205701581
724 22086732
406 77065874
300 1000000000
90 292435206
406 292357986
629 25271546
730 6180070
581 33634686
969 6655599
155 30393035
505 2756660
87 102123183
171 5882145
322 32732173
56 179462610
330 85963871
350 99607620
617 113644447
871 24216565
301 91305111
985 51209600
984 144547783
830 1000000000
97 53136542
853 97046435
272 98644753
950 66321297
476 1000000000
113 403065989
831 85888820
414 108301757
504 4512674
741 298283704
119 831639798
174 1000000000
412 10616771
761 151291557
208 1000000000
558 1000000000
897 3193656
213 157822622
272 25241447
118 256068601
85 231929374
202 347058721
561 216126067
399 596677657
242 33378600
63 124969945
562 759447428
64 786964651
703 394361873
300 199445615
147 450748045
2 44685898
413 33341682
761 19283559
540 220491732
195 3095979
954 186533550
479 38190112
782 1000000000
733 492149618
952 190616289
405 89030451
656 365619805
311 87093697
502 137350470
83 57429262
250 74651371
313 6492635
157 127167995
858 1000000000
789 2521597
908 446215035
267 6142194
344 105282686
960 3993284
839 25618414
354 554129297
295 1000000000
851 15568902
162 27426945
689 202468229
182 33002000
830 1000000000
365 146403876
809 846807197
110 129119557
585 3017266
265 299704197
248 44335022
381 265379630
245 79454970
892 265697088
552 133385936
309 34148805
9 143139165
376 66365037
400 34911510
838 239342057
381 547167208
749 623746784
385 1000000000
86 93933909
586 20595250
9 217346879
233 47318933
527 238103044
63 27679826
806 11296707
538 209778105
384 337438213
428 766970561
835 163643541
683 88000004
409 73804186
769 190850394
376 114766391
693 162085923
394 764127685
998 317238008
998 3595169
734 494355585
772 1000000000
444 872142
676 115581214
984 502963077
878 159750872
394 74977196
722 235249416
986 253853118
944 989976718
952 7051928
440 43812596
340 428435345
778 337794961
439 13791260
943 299129456
847 2023427
37 244592280
349 385730907
317 73619889
250 1000000000
224 283254813
324 1000000000
421 259506584
821 909803416
843 71526069
812 5251545
156 130115892
640 28641062
567 1415577
611 220972590
691 356216594
796 133740939
570 198686492
875 274934997
155 1000000000
960 340699
222 231363337
507 262146399
939 249197819
332 33946839
874 305476065
787 62180638
820 135798739
464 52149238
191 30987575
804 1000000000
484 368555563
933 751478809
475 163840703
668 334714174
77 521807638
394 354811008
888 223298222
941 17978225
86 338852855
63 346520526
374 142527780
399 277525495
7 124713896
860 1000000000
835 285433485
208 72393495
241 11084998
250 1000000000
961 251290191
594 1000000000
763 16448779
200 60803013
87 1000000000
372 53213995
213 37776211
838 24212213
525 62854122
6 645956073
111 175058391
356 153637602
163 661969427
513 16726572
281 62923329
323 58779919
570 1000000000
883 557902692
52 66359800
186 1000000000
249 319268305
374 44308396
343 136332625
273 47574758
880 593851183
474 206057665
595 320061343
936 53826610
599 206206519
693 1000000000
718 137284031
744 8258353
783 920629349
857 55933204
898 211728390
480 58314969
695 10055450
525 303403724
94 42494742
248 446551250
87 90679170
201 44831879
330 340900736
456 1000000000
808 230572401
61 792948329
311 206615456
769 257533800
560 1000000000
282 15479499
836 257886007
930 212651566
49 60750410
279 262292607
25 14236024
667 91185623
914 43640827
980 123982158
454 424404155
348 505871948
492 172418198
154 72241200
676 11177883
86 438441217
389 58091748
120 95809959
873 964533376
144 6174324
887 443195845
118 968489951
39 66863462
370 156124441
946 1000000000
12 275634014
558 1000000000
780 636489
532 874334704
226 216439
596 11980023
455 46479515
55 861540822
41 1000000000
571 320362012
10 25134874
938 217082044
288 39788634
242 244652123
877 341966114
525 189765991
855 719678214
209 46322443
992 1000000000
744 155450752
631 190479248
969 450587355
588 816083768
700 524570418
463 49026805
609 75792020
368 382079126
496 124423229
791 176589856
361 16963310
468 155116373
580 292800039
551 39754115
385 77040989
680 23912175
376 330439805
111 166852464
250 8891818
269 687015
301 1000000000
944 1000000000
371 304102609
506 629201543
442 1000000000
905 7275721
660 1000000000
599 100374677
95 29951484
722 64727558
501 130865401
124 72464269
541 150264343
244 624181282
526 66146136
882 792101793
282 36547566
694 244430406
344 245683362
631 223549
920 144115027
96 114633990
962 12913988
510 447325169
22 273913336
834 31036852
557 26505688
460 57394844
477 4393140
588 496492215
839 615709677
843 9346829
708 1000000000
111 292878095
802 345770158
57 1827522
890 138987954
90 459239011
925 140549375
537 269404983
106 11867013
173 9117804
96 495820492
872 45793617
489 666581805
289 13877734
636 523330491
792 1000000000
321 718286
444 1991767
440 13057995
951 33530805
385 19511670
920 585825795
444 1000000000
992 39753239
9 53697492
701 451890806
296 286273335
272 206993275
697 485737106
153 749304715
669 1000000000
392 181268044
306 1000000000
950 40133194
545 84540047
825 332010844
51 102883567
203 194524366
534 198176346
114 18454976
92 86372760
808 204029593
852 39896101
900 294926308
333 19191640
318 370433948
113 279295196
861 1000000000
831 149838180
147 728952522
391 12040188
967 406191671
265 83432248
265 28853710
725 955522763
489 27894992
3 103193148
560 362985696
499 73976791
476 971154047
606 39653207
966 576458822
554 164039358
822 12947739
608 855195558
773 276891987
961 1000000000
121 44148722
843 298668670
836 144473376
760 444366079
876 49665533
86 83466939
139 27167446
663 1000000000
664 164315236
522 490539189
3 34026766
415 731627899
843 66580458
934 134066884
538 107090500
758 377656
887 145886905
305 46905949
210 179456000